Approximate iterations for structured matrices. (English) Zbl 1144.65029
The paper deals with the evaluation of a matrix-valued function \(f(A)\), where \(A\) is a large matrix with a special structure. The authors present a transformation of an iterative fixed-point like process, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. Applications are also given for \(f(A) = A^{-1}\) and \(f(A) = \sqrt{A}\).
Reviewer: Constantin Popa (Constanţa)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
References:
| [1] | Alpert B., Beylkin G., Gines D. and Vozovoi L. (2002). Adaptive solution of partial differential equations in multiwavelet bases. J. Comput. Phys. 182: 149–190 · Zbl 1015.65046 · doi:10.1006/jcph.2002.7160 |
| [2] | Bebendorf M. and Hackbusch W. (2003). Existence of \({\mathcal{H} }\) -matrix approximants to the inverse FE-matrix of elliptic operators with L coefficients. Numer. Math. 95: 1–28 · Zbl 1033.65100 · doi:10.1007/s00211-002-0445-6 |
| [3] | Beylkin G., Coult N. and Mohlenkamp M.J. (1999). Fast spectral projection algorithms for density-matrix computations. J. Comput. Phys. 152: 32–54 · Zbl 0945.65049 · doi:10.1006/jcph.1999.6215 |
| [4] | Beylkin G. and Mohlenkamp M.M. (2002). Numerical operator calculus in higher dimensions. Proc. Natl. Acad. Sci. USA 99: 10246–10251 · Zbl 1008.65026 · doi:10.1073/pnas.112329799 |
| [5] | Beylkin G. and Mohlenkamp M.M. (2005). Algorithms for numerical analysis in high dimensions. SIAM J. Sci. Comput. 26: 2133–2159 · Zbl 1085.65045 · doi:10.1137/040604959 |
| [6] | Beylkin G. and Sandberg K. (2005). Wave propagation using bases for bandlimited functions. Wave Motion 41: 263–291 · Zbl 1189.76456 · doi:10.1016/j.wavemoti.2004.05.008 |
| [7] | Bhatia R. (1996). Matrix Analysis. Springer, New York · Zbl 0863.15001 |
| [8] | Bini D.A., Tyrtyshnikov E.E., Yalamov P. (eds) (2001). Structured Matrices: Recent Developments in Theory and Computation. Advances in Computation. Nova Science, Huntington · Zbl 1008.15003 |
| [9] | Bini D.A. and Meini B. (2001). Solving block banded block Toeplitz systems with structured blocks: algorithms and applications. In: Bini, D.A., Tyrtyshnikov, E.E. and Yalamov, P. (eds) Structured Matrices: Recent Developments in Theory and Computation. Advances in Computation. Nova Science, Huntington · Zbl 0966.65028 |
| [10] | Byers R., He C. and Mehrmann V. (1997). The matrix sign function method and the computation of invariant subspaces. SIMAX 18: 615–632 · Zbl 0874.65031 |
| [11] | De Lathauwer L., De Moor B. and Vandewalle J. (2000). A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21: 1253–1278 · Zbl 0962.15005 · doi:10.1137/S0895479896305696 |
| [12] | Ford J.M. and Tyrtyshnikov E.E. (2003). Combining Kronecker product approximation with discrete wavelet transforms to solve dense, function-related systems. SIAM J. Sci. Comp. 25: 961–981 · Zbl 1046.65020 · doi:10.1137/S1064827503421689 |
| [13] | Ford J.M., Oseledets I.V. and Tyrtyshnikov E.E. (2004). Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids. Russ. J. Numer. Math. Math. Model. 19(2): 185–204 · Zbl 1055.65152 · doi:10.1515/156939804323089334 |
| [14] | Gavrilyuk I.P., Hackbusch W. and Khoromskij B.N. (2005). Data-sparse approximation to a class of operator-valued functions. Math. Comp. 74: 681–708 · Zbl 1066.65060 · doi:10.1090/S0025-5718-04-01703-X |
| [15] | Gavrilyuk I.P., Hackbusch W. and Khoromskij B.N. (2005). Tensor-product approximation to elliptic and parabolic solution operators in higher dimensions. Computing 74: 131–157 · Zbl 1071.65032 · doi:10.1007/s00607-004-0086-y |
| [16] | Goreinov S.A., Tyrtyshnikov E.E. and Yeremin A.Y. (1996). Matrix-free iteration solution strategies for large dense linear systems. Numer. Linear Algebra Appl. 4: 1–22 · Zbl 0889.65031 |
| [17] | Goreinov S.A., Tyrtyshnikov E.E. and Zamarashkin N.L. (1997). A theory of pseudo-skeleton approximations. Linear Algebra Appl. 261: 1–21 · Zbl 0877.65021 · doi:10.1016/S0024-3795(96)00301-1 |
| [18] | Grasedyck L. (2004). Existence and computation of a low Kronecker-rank approximation to the solution of a tensor system with tensor right-hand side. Computing 72: 247–265 · Zbl 1058.65036 · doi:10.1007/s00607-003-0037-z |
| [19] | Grasedyck L. and Hackbusch W. (2003). Construction and arithmetics of \({\mathcal{H}}\) -matrices. Computing 70: 295–334 · Zbl 1030.65033 · doi:10.1007/s00607-003-0019-1 |
| [20] | Grasedyck L., Hackbusch W. and Khoromskij B.N. (2003). Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices. Computing 70: 121–165 · Zbl 1239.65026 · doi:10.1007/s00607-002-1470-0 |
| [21] | Hackbusch W. (1999). A sparse matrix arithmetic based on \({\mathcal{H}}\) -matrices. I. Introduction to \({\mathcal{H}}\) -matrices. Computing 62: 89–108 · Zbl 0927.65063 · doi:10.1007/s006070050015 |
| [22] | Hackbusch W. and Khoromskij B.N. (2000). A sparse \({\mathcal{H}}\) -matrix arithmetic. II. Application to multi-dimensional problems. Computing 64: 21–47 · Zbl 0962.65029 |
| [23] | Hackbusch W. and Khoromskij B.N. (2000). A sparse \({\mathcal{H}}\) -matrix arithmetic: General complexity estimates. J. Comp. Appl. Math. 125: 479–501 · Zbl 0977.65036 · doi:10.1016/S0377-0427(00)00486-6 |
| [24] | Hackbusch W. and Khoromskij B.N. (2006). Low-rank Kronecker product approximation to multi-dimensional nonlocal operators. Part I. Separable approximation of multi-variate functions. Computing 76: 177–202 · Zbl 1087.65049 · doi:10.1007/s00607-005-0144-0 |
| [25] | Hackbusch W. and Khoromskij B.N. (2006). Low-rank Kronecker product approximation to multi-dimensional nonlocal operators. Part II. HKT representations of certain operators. Computing 76: 203–225 · Zbl 1087.65050 · doi:10.1007/s00607-005-0145-z |
| [26] | Hackbusch W., Khoromskij B.N. and Kriemann R. (2004). Hierarchical matrices based on a weak admissibility criterion. Computing 73: 207–243 · Zbl 1063.65035 · doi:10.1007/s00607-004-0080-4 |
| [27] | Hackbusch W., Khoromskij B.N. and Tyrtyshnikov E.E. (2005). Hierarchical Kronecker tensor-product approximations. J. Numer. Math. 13: 119–156 · Zbl 1081.65035 · doi:10.1515/1569395054012767 |
| [28] | Higham N.J. (1986). Newton’s method for the matrix square root. Math. Comput. 46: 537–549 · Zbl 0614.65045 |
| [29] | Higham N.J. (1997). Stable iterations for the matrix square root. Numer. Algorithms 15: 227–242 · Zbl 0884.65035 · doi:10.1023/A:1019150005407 |
| [30] | Kenney C.S. and Laub A.J. (1995). The matrix sign function. IEEE Trans. Automat. Control 40: 1330–1348 · Zbl 0830.93022 · doi:10.1109/9.402226 |
| [31] | Olshevsky V., Oseledets I. and Tyrtyshnikov E.E. (2006). Tensor properties of multilevel Toeplitz and related matrices. Linear Algebra Appl. 412: 1–21 · Zbl 1082.15044 · doi:10.1016/j.laa.2005.03.040 |
| [32] | Oseledets, I.V., Tyrtyshnikov, E.E.: Approximate inversion of matrices in the process of solving a hypersingular integral equation. Comp. Math. Math. Phys. 45(2), 302–313 (2005) (translated from JVM i MF 45(2), 315–326 (2005)) · Zbl 1073.65569 |
| [33] | Pan V.Y. and Rami Y. (2001). Newton’s iteration for the inversion of structured matrices. In: Bini, D.A., Tyrtyshnikov, E.E. and Yalamov, P. (eds) Structured Matrices: Recent Developments in Theory and Computation. Advances in Computation, pp 79–90. Nova Science, Huntington |
| [34] | Schulz G. (1933). Iterative Berechnung der reziproken Matrix. ZAMM 13: 57–59 · JFM 59.0535.04 · doi:10.1002/zamm.19330130111 |
| [35] | Stewart G.W. and Sun J. (1990). Matrix Perturbation Theory. Academic Press, San Diego · Zbl 0706.65013 |
| [36] | Tyrtyshnikov, E.E.: Tensor approximations of matrices generated by asymptotically smooth functions. Sbornik: Mathematics 194(5–6), 941–954 (2003) (translated from Mat. Sb. 194(6), 146–160 (2003)) · Zbl 1067.65044 |
| [37] | Tyrtyshnikov E.E. (2004). Kronecker-product approximations for some function-related matrices. Linear Algebra Appl. 379: 423–437 · Zbl 1046.65033 · doi:10.1016/j.laa.2003.08.013 |
| [38] | Tyrtyshnikov, E.E.: Mosaic ranks and skeletons. In: Numerical Analysis and Its Applications. Proceedings of WNAA-96. Lecture Notes in Computer Science, vol. 1196, pp. 505–516. Springer, Berlin (1996) |
| [39] | Tyrtyshnikov E.E. (1996). Mosaic-skeleton approximations. Calcolo 33: 47–57 · Zbl 0906.65048 · doi:10.1007/BF02575706 |
| [40] | Tyrtyshnikov E.E. (2000). Incomplete cross approximation in the mosaic-skeleton method. Computing 64: 367–380 · Zbl 0964.65048 · doi:10.1007/s006070070031 |
| [41] | Wilkinson J.H. (1963). Rounding Errors in Algebraic Processes. Prentice Hall, Englewood Cliffs, NJ · Zbl 1041.65502 |
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.
