In this note, we revisit the result of the Toeplitz matrix inversion formula proposed by Lv and Huang (2007), then we give a new structured perturbation analysis, which is useful for testing the ...stability of practical algorithms. It has been shown that our new upper bound is much sharper than the one they have given, especially when the size of the Toeplitz matrix is very large. Numerical experiments illustrate the effectiveness of our theoretical results.
A strong-form boundary collocation method, the singular boundary method (SBM), is developed in this paper for the wave propagation analysis at low and moderate wavenumbers in periodic structures. The ...SBM is of several advantages including mathematically simple, easy-to-program, meshless with the application of the concept of origin intensity factors in order to eliminate the singularity of the fundamental solutions and avoid the numerical evaluation of the singular integrals in the boundary element method. Due to the periodic behaviors of the structures, the SBM coefficient matrix can be represented as a block Toeplitz matrix. By employing three different fast Toeplitz-matrix solvers, the computational time and storage requirements are significantly reduced in the proposed SBM analysis. To demonstrate the effectiveness of the proposed SBM formulation for wave propagation analysis in periodic structures, several benchmark examples are presented and discussed The proposed SBM results are compared with the analytical solutions, the reference results and the COMSOL software.
Covariance matrices in SIMO technology are used to solve channel identification problems. We obtain an upper bound for the generalised condition number of covariance matrix in this article. The ...existing notion of preconditioners in 1, 2 is extended to the singular matrices. We compare existing preconditioners for non-singular matrices and the generalised preconditioners. We observe that generalised preconditioners have better performance from numerical experiments. Also, the generating function of the covariance matrix is calculated, and spectral properties are derived using only linear algebra techniques.
The results on the inversion of convolution operators as well as Toeplitz (and block Toeplitz) matrices in the 1-D (one-dimensional) case are classical and have numerous applications. Last year, we ...considered the 2-D case of Toeplitz-block Toeplitz (TBT) matrices, described a minimal information, which is necessary to recover the inverse matrices, and gave a complete characterisation of the inverse matrices. Now, we develop our approach for the more complicated cases of the block TBT-matrices and of the 3-D Toeplitz matrices. Some important special cases are treated as well.
The main aim of this paper is to apply the Galerkin finite element method to numerically solve the nonlinear fractional Schrödinger equation with wave operator. We first construct a fully discrete ...scheme combining the Crank–Nicolson method with the Galerkin finite element method. Two conserved quantities of the discrete system are shown. Meanwhile, the prior bound of the discrete solutions are proved. Then, we prove that the discrete scheme is unconditionally convergent in the senses of L2−norm and Hα/2−norm. Moreover, by the proposed iterative algorithm, some numerical examples are given to verify the theoretical results and show the effectiveness of the numerical scheme. Finally, a fast Krylov subspace solver with suitable circulant preconditioner is designed to solve above Toeplitz-like linear system. In each iterative step, this method can effectively reduce the memory requirement of the proposed iterative finite element scheme from O(M2) to O(M), and the computational complexity from O(M3) to O(MlogM), where M is the number of grid nodes. Several numerical tests are carried out to show that this fast algorithm is more practical than the traditional backslash and LU factorization methods, in terms of memory requirement and computational cost.
In this paper we consider a family of tetradiagonal (= four non-zero diagonals) Toeplitz matrices with a limiting set consisting in one analytic arc only and obtain individual asymptotic expansions ...for all the eigenvalues, as the matrix size goes to infinity. Additionally, we provide specific expansions for the extreme eigenvalues which are the eigenvalues approaching the extreme points of the limiting set. In contrast to previous related works, we study non-Hermitian Toeplitz matrices having non-canonical distribution and a real limiting set. The considered family does not belong to the so-called simple-loop class, nevertheless we manage to extend the theory to this case. The achieved formulas reveal the fine details of the eigenvalue structure and allow us to directly calculate high accuracy eigenvalues, even for matrices of relatively small size.
In Lin et al. (2021) 21 and Zhao et al. (2023) 37, two-sided preconditioning techniques are proposed for non-local evolutionary equations, which possesses (i) mesh-size independent theoretical bound ...of condition number of the two-sided preconditioned matrix; (ii) small and stable iteration numbers in numerical tests. In this paper, we modify the two-sided preconditioning by multiplying the left-sided and the right-sided preconditioners together as a single-sided preconditioner. Such a single-sided preconditioner essentially derives from approximating the spatial matrix with a fast diagonalizable matrix and keeping the temporal matrix unchanged. Clearly, the matrix-vector multiplication of the single-sided preconditioning is faster to compute than that of the two-sided one, since the single-sided preconditioned matrix has a simpler structure. More importantly, we show theoretically that the single-sided preconditioned generalized minimal residual (GMRES) method has a convergence rate no worse than the two-sided preconditioned one. As a result, the one-sided preconditioned GMRES solver requires less computational time than the two-sided preconditioned GMRES solver in total. Numerical results are reported to show the efficiency of the proposed single-sided preconditioning technique.
•The operation cost for implementing the single-sided preconditioner is linearithmic, which is nearly optimal.•The single-sided preconditioner is shown to be better than the two-sided one by theoretical and numerical evidences.•The iteration number of the proposed preconditioning technique is not sensitive to the parameters of the problem.•The complexity of the proposed solver is linearithmic, which is nearly optimal.
The Vandermonde decomposition of Toeplitz matrices, discovered by Carathéodory and Fejér in the 1910s and rediscovered by Pisarenko in the 1970s, forms the basis of modern subspace methods for 1-D ...frequency estimation. Many related numerical tools have also been developed for multidimensional (MD), especially 2-D, frequency estimation; however, a fundamental question has remained unresolved as to whether an analog of the Vandermonde decomposition holds for multilevel Toeplitz matrices in the MD case. In this paper, an affirmative answer to this question and a constructive method for finding the decomposition are provided when the matrix rank is lower than the dimension of each Toeplitz block. A numerical method for searching for a decomposition is also proposed when the matrix rank is higher. The new results are applied to study the MD frequency estimation within the recent super-resolution framework. A precise formulation of the atomic \ell _{0} norm is derived using the Vandermonde decomposition. Practical algorithms for frequency estimation are proposed based on the relaxation techniques. Extensive numerical simulations are provided to demonstrate the effectiveness of these algorithms compared with the existing atomic norm and subspace methods.
Distributed matrix computations - matrix-matrix or matrix-vector multiplications - are well-recognized to suffer from the problem of stragglers (slow or failed worker nodes). Much of prior work in ...this area is (i) either sub-optimal in terms of its straggler resilience, or (ii) suffers from numerical problems, i.e., there is a blow-up of round-off errors in the decoded result owing to the high condition numbers of the corresponding decoding matrices. Our work presents a convolutional coding approach to this problem that removes these limitations. It is optimal in terms of its straggler resilience, and has excellent numerical robustness as long as the workers' storage capacity is slightly higher than the fundamental lower bound. Moreover, it can be decoded using a fast peeling decoder that only involves add/subtract operations. Our second approach has marginally higher decoding complexity than the first one, but allows us to operate arbitrarily close to the storage capacity lower bound. Its numerical robustness can be theoretically quantified by deriving a computable upper bound on the worst case condition number over all possible decoding matrices by drawing connections with the properties of large block Toeplitz matrices. All above claims are backed up by extensive experiments done on the AWS cloud platform.
PDF
