Factorizing complex symmetric matrices with positive definite real and imaginary parts

Higham, Nicholas

doi:10.1090/S0025-5718-98-00978-8

Factorizing complex symmetric matrices with positive definite real and imaginary parts

Author: Nicholas J. Higham
Journal: Math. Comp. 67 (1998), 1591-1599
MSC (1991): Primary 65F05
DOI: https://doi.org/10.1090/S0025-5718-98-00978-8
MathSciNet review: 1474652
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Complex symmetric matrices whose real and imaginary parts are positive definite are shown to have a growth factor bounded by 2 for LU factorization. This result adds to the classes of matrix for which it is known to be safe not to pivot in LU factorization. Block $\mathrm {LDL^T}$ factorization with the pivoting strategy of Bunch and Kaufman is also considered, and it is shown that for such matrices only $1\times 1$ pivots are used and the same growth factor bound of 2 holds, but that interchanges that destroy band structure may be made. The latter results hold whether the pivoting strategy uses the usual absolute value or the modification employed in LINPACK and LAPACK.

E. Anderson, Z. Bai, C. H. Bischof, J. W. Demmel, J. J. Dongarra, J. J. Du Croz, A. Greenbaum, S. J. Hammarling, A. McKenney, S. Ostrouchov, and D. C. Sorensen, LAPACK users’ guide, Release 2.0, second ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1995.

James R. Bunch and Linda Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp. 31 (1977), no. 137, 163–179. MR 428694, DOI https://doi.org/10.1090/S0025-5718-1977-0428694-0

Jane K. Cullum and Ralph A. Willoughby, A $QL$ procedure for computing the eigenvalues of complex symmetric tridiagonal matrices, SIAM J. Matrix Anal. Appl. 17 (1996), no. 1, 83–109. MR 1372924, DOI https://doi.org/10.1137/S0895479894137639

J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart, LINPACK users’ guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1979.

Jack J. Dongarra, Iain S. Duff, Danny C. Sorensen, and Henk A. van der Vorst, Solving linear systems on vector and shared memory computers, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. MR 1084164

Graeme Fairweather, A note on the efficient implementation of certain Padé methods for linear parabolic problems, BIT 18 (1978), no. 1, 106–109. MR 488820, DOI https://doi.org/10.1007/BF01947749

Roland W. Freund, Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices, SIAM J. Sci. Statist. Comput. 13 (1992), no. 1, 425–448. MR 1145195, DOI https://doi.org/10.1137/0913023

Philip E. Gill, Michael A. Saunders, and Joseph R. Shinnerl, On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 1, 35–46. MR 1372921, DOI https://doi.org/10.1137/S0895479893252623

Gene H. Golub and Charles Van Loan, Unsymmetric positive definite linear systems, Linear Algebra Appl. 28 (1979), 85–97. MR 549423, DOI https://doi.org/10.1016/0024-3795%2879%2990122-8

Emilie V. Haynsworth, Determination of the inertia of a partitioned Hermitian matrix, Linear Algebra Appl. 1 (1968), no. 1, 73–81. MR 223392, DOI https://doi.org/10.1016/0024-3795%2868%2990050-5

Nicholas J. Higham, The Test Matrix Toolbox for Matlab (version 3.0), Numerical Analysis Report No. 276, Manchester Centre for Computational Mathematics, Manchester, England, September 1995.

Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629

Mark T. Jones and Merrell L. Patrick, Bunch–Kaufman factorization for real symmetric indefinite banded matrices, SIAM J. Matrix Anal. Appl. 14 (1993), no. 2, 553–559.

Mark T. Jones and Merrell L. Patrick, Factoring symmetric indefinite matrices on high-performance architectures, SIAM J. Matrix Anal. Appl. 15 (1994), no. 1, 273–283. MR 1257634, DOI https://doi.org/10.1137/S089547989018008X

Roy Mathias, Matrices with positive definite Hermitian part: inequalities and linear systems, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 640–654. MR 1152771, DOI https://doi.org/10.1137/0613038

Giorgio Moro and Jack H. Freed, Calculation of ESR spectra and related Fokker-Planck forms by the use of the Lanczos algorithm, J. Chem. Phys. 74 (1981), no. 7, 3757–3773. MR 610918, DOI https://doi.org/10.1063/1.441604

D. Schmitt, B. Steffen, and T. Weiland, 2D and 3D computations of lossy eigenvalue problems, IEEE Trans. Magnetics 30 (1994), no. 5, 3578–3581.

Steven M. Serbin, On factoring a class of complex symmetric matrices without pivoting, Math. Comp. 35 (1980), no. 152, 1231–1234. MR 583500, DOI https://doi.org/10.1090/S0025-5718-1980-0583500-9

Robert J. Vanderbei, Symmetric quasidefinite matrices, SIAM J. Optim. 5 (1995), no. 1, 100–113. MR 1315706, DOI https://doi.org/10.1137/0805005

H. A. Van Der Vorst and J. B. M. Melissen, A Petrov–Galerkin type method for solving $Ax=b$, where $A$ is symmetric complex, IEEE Trans. Magnetics 26 (1990), no. 2, 706–708.