Applications of statistical condition estimation to the solution of linear systems. (English) Zbl 1212.65130
Author’s abstract: This paper discusses an estimation of the conditioning of the problem of solving linear systems with a technique called statistical condition estimation (SCE). It has two main parts, one on structured linear problems and one on large sparse problems. Specifically, triangular and bidiagonal matrices are studied in some detail as typical of structured matrices. Such a structure, when properly respected, leads to condition estimates that are much less conservative compared with traditional non-statistical methods of condition estimation. Some examples of linear systems and Sylvester equations are presented. Vandermonde and Cauchy matrices are also studied as representative of linear systems with large condition numbers that can nonetheless be solved accurately. SCE reflects this. Moreover, SCE when applied to solving very large linear systems by iterative solvers, including conjugate gradient and multigrid methods, performs equally well and various examples are given to illustrate the performance. SCE for solving large linear systems with direct methods, such as methods for semi-separable structures, are also investigated. In all cases, the advantages of using SCE are manifold: ease of use, efficiency, and reliability.
Reviewer: J. D. Tebbens (Praha)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 15A12 | Conditioning of matrices |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
Keywords:
structured linear systems; sparse large linear systems; conditioning; statistical condition estimations; Vandermonde and Cauchy matrices; Sylvester equations; iterative solvers; conjugate gradient; multigrid methods; direct methodsReferences:
| [1] | Kenney, Small-sample statistical condition estimates for general matrix functions, SIAM Journal on Scientific Computing 15 pp 36– (1994) · Zbl 0801.65042 |
| [2] | Kenney, Statistical condition estimation for linear systems, SIAM Journal on Scientific Computing 19 pp 566– (1998) · Zbl 0915.15003 |
| [3] | Higham, Backward error and condition of structured linear systems, SIAM Journal on Matrix Analysis and Applications 13 pp 162– (1992) · Zbl 0747.65028 |
| [4] | Gohberg, Mixed, componentwise, and structured condition numbers, SIAM Journal on Matrix Analysis and Applications 14 pp 688– (1993) · Zbl 0780.15004 |
| [5] | Rump, Structured perturbations. Part II: componentwise distances, SIAM Journal on Matrix Analysis and Applications 25 pp 31– (2003) |
| [6] | Gudmundsson, Small-sample statistical estimates for matrix norms, SIAM Journal on Matrix Analysis and Applications 16 pp 776– (1995) · Zbl 0831.65051 |
| [7] | Anderson, LAPACK Users’ Guide (1999) · Zbl 0934.65030 · doi:10.1137/1.9780898719604 |
| [8] | Hager, Condition estimates, SIAM Journal on Scientific Computing 5 pp 311– (1984) · Zbl 0542.65023 |
| [9] | Higham, A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra, SIAM Journal on Matrix Analysis and Applications 21 pp 1185– (2000) · Zbl 0959.65061 |
| [10] | Higham, Algorithm 674: FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software 14 pp 381– (1988) · Zbl 0900.65124 |
| [11] | Byers, LINPACK-style condition estimator for the equation AX-XBT=C, IEEE Transactions on Automatic Control 29 pp 926– (1984) · Zbl 0544.65027 |
| [12] | Bartels, Solution of the matrix equation AX+XB=C, Communications of the ACM 15 pp 820– (1972) · Zbl 1372.65121 |
| [13] | Golub, A Hessenberg-Schur method for the problem AX+XB=C, IEEE Transactions on Automatic Control 24 pp 909– (1979) |
| [14] | Pei, A test matrix for inversion procedures, Communications of the ACM 5 pp 508– (1962) |
| [15] | Sharpe, Rings and Factorization (1987) · Zbl 0674.13008 · doi:10.1017/CBO9780511565960 |
| [16] | Gautschi, Lower bounds for the condition number of Vandermonde matrices, Numerische Mathematik 52 pp 241– (1988) · Zbl 0646.15003 |
| [17] | Björck, Solution of Vandermonde systems of equations, Mathematics of Computation 24 pp 893– (1970) |
| [18] | Higham, Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems, Numerische Mathematik 50 pp 613– (1987) · Zbl 0595.65029 |
| [19] | Davis, Interpolation and Approximation (1975) |
| [20] | Briggs, A Multigrid Tutorial (2000) · Zbl 0958.65128 · doi:10.1137/1.9780898719505 |
| [21] | Concus, Sparse Matrix Computations (1976) |
| [22] | Axelsson, On the rate of convergence of the preconditioned conjugate gradient algorithm, Numerische Mathematik 48 pp 499– (1986) · Zbl 0564.65017 |
| [23] | Beckermann, Superlinear convergence of conjugate gradients, SIAM Journal on Numerical Analysis 39 pp 300– (2001) · Zbl 0997.65058 |
| [24] | van der Sluis, The rate of convergence of conjugate gradients, Numerische Mathematik 48 pp 543– (1986) · Zbl 0596.65015 |
| [25] | Notay, On the convergence rate of the conjugate gradients in presence of rounding errors, Numerische Mathematik 65 pp 301– (1993) · Zbl 0791.65016 |
| [26] | Demmel, Applied Numerical Linear Algebra (1997) · doi:10.1137/1.9781611971446 |
| [27] | Chandrasekaran, Some fast algorithms for sequentially semiseparable representations, SIAM Journal on Numerical Analysis 27 pp 341– (2005) · Zbl 1091.65063 |
| [28] | Chandrasekaran, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM Journal on Matrix Analysis and Applications 28 pp 603– (2006) · Zbl 1120.65031 |
| [29] | Xia J. Fast direct solvers for structured linear systems of equations. Ph.D. Thesis, UC Berkeley, 2006. |
| [30] | Chandrasekaran S, Gu M, Li XS, Vesselevski P. Schur-monotonic semi-separable approximations of symmetric positive definite matrices. Research Notes, 2006. |
| [31] | Chandrasekaran S, Gu M, Li XS, Xia J. Schur-monotonic HSS approximations of symmetric positive definite matrices. Research Notes, 2006. |
| [32] | Duff, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Transactions on Mathematical Software 9 pp 302– (1983) · Zbl 0515.65022 |
| [33] | Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review 34 pp 82– (1992) · Zbl 0919.65019 |
| [34] | George, Nested dissection of a regular finite element mesh, SIAM Journal on Numerical Analysis 10 pp 345– (1973) · Zbl 0259.65087 |
| [35] | George, Computer Solution of Large Sparse Positive Definite Systems (1981) · Zbl 0516.65010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
