The standard implementation of the hybrid GMRES algorithm for solving large nonsymmetric linear systems involves a Gram-Schmidt process which is a potential source of significant numerical error. An alternative implem...The standard implementation of the hybrid GMRES algorithm for solving large nonsymmetric linear systems involves a Gram-Schmidt process which is a potential source of significant numerical error. An alternative implementation is outlined here in which orthogonalization by Householder transformations replaces the Gram-Schmidt process. Numerical experiments show that the new implementation is more stable.展开更多
A fast Cholesky decomposition and a fast inverse Cholesky decomposition method for A T A are presented,where A is an m×n rectangular Toeplitz block matrix,we give the FCD algorithm for computing...A fast Cholesky decomposition and a fast inverse Cholesky decomposition method for A T A are presented,where A is an m×n rectangular Toeplitz block matrix,we give the FCD algorithm for computing R , and the FICD algorithm for computing R -1 ,both allow for an efficient parallel implementation,for solving a least squares problem and require only O(mn) operations.展开更多
A fast Cholesky factorization algorithm based on the classical Schur algorithm for themp×mp symmetric positive definite (s. p. d) block-Toeplitz matrices is presented. The relation between the generator and the S...A fast Cholesky factorization algorithm based on the classical Schur algorithm for themp×mp symmetric positive definite (s. p. d) block-Toeplitz matrices is presented. The relation between the generator and the Schur complement of the matrices is explored. Besides, by applying the hyperbolic Householder transformations, we can reach an improved algorithm whose computational complexity is2p 2m3?4pm3+3/2m3+O(pm).展开更多
A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be...A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be computed in parallel using the sametransformation.We also prove that some kind of Toeplltz-block matrices can he transformed into the corresponding block-Toeplitz matrices.展开更多
The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 20...The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T, G, and M-type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3<sup>(N-1)</sup>, for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.展开更多
The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which o...The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which only little is known up to now. This is different from some mature algorithms, that are clearly limited only to medium-sized matrix for calculating full spectrum. It is hoped that a combination of this paper with the earlier works, to be seen soon, may provide some effective algorithms for computing the spectrum in practice, especially for matrix mechanics.展开更多
A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):...A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):433–437,1963)as a tool to obtain a tridiagonal matrix similar to a given square matrix.Some of the free parameters of the transformation can be chosen to attain better numerical properties.In this work,we study the spectral properties of the transformation.We also propose a special choice for free coefficients of that transformation to minimize its condition number.The transformation with such suitable choice of parameters is called optimal.展开更多
文摘The standard implementation of the hybrid GMRES algorithm for solving large nonsymmetric linear systems involves a Gram-Schmidt process which is a potential source of significant numerical error. An alternative implementation is outlined here in which orthogonalization by Householder transformations replaces the Gram-Schmidt process. Numerical experiments show that the new implementation is more stable.
文摘A fast Cholesky decomposition and a fast inverse Cholesky decomposition method for A T A are presented,where A is an m×n rectangular Toeplitz block matrix,we give the FCD algorithm for computing R , and the FICD algorithm for computing R -1 ,both allow for an efficient parallel implementation,for solving a least squares problem and require only O(mn) operations.
文摘A fast Cholesky factorization algorithm based on the classical Schur algorithm for themp×mp symmetric positive definite (s. p. d) block-Toeplitz matrices is presented. The relation between the generator and the Schur complement of the matrices is explored. Besides, by applying the hyperbolic Householder transformations, we can reach an improved algorithm whose computational complexity is2p 2m3?4pm3+3/2m3+O(pm).
文摘A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be computed in parallel using the sametransformation.We also prove that some kind of Toeplltz-block matrices can he transformed into the corresponding block-Toeplitz matrices.
文摘The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T, G, and M-type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3<sup>(N-1)</sup>, for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.
基金This work was supported in part by the National Natural Science Foundation of China(Grant Nos.12090011,11771046,11771188,11771189)the National Key R&D Program of China(No.2020YFA0712900)+1 种基金the Natural Science Foundation of Jiangsu Province(Grant No.BK20171162)the project from the Ministry of Education in China,and the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which only little is known up to now. This is different from some mature algorithms, that are clearly limited only to medium-sized matrix for calculating full spectrum. It is hoped that a combination of this paper with the earlier works, to be seen soon, may provide some effective algorithms for computing the spectrum in practice, especially for matrix mechanics.
基金The work of the first and third authors was partially supported by National Council for Scientific and Technological Development(CNPq),Brazil.
文摘A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):433–437,1963)as a tool to obtain a tridiagonal matrix similar to a given square matrix.Some of the free parameters of the transformation can be chosen to attain better numerical properties.In this work,we study the spectral properties of the transformation.We also propose a special choice for free coefficients of that transformation to minimize its condition number.The transformation with such suitable choice of parameters is called optimal.
