Homotopic residual correction processes

Pan, V.; Kunin, M.; Rosholt, R.; Kodal, H.

doi:10.1090/S0025-5718-05-01771-0

Homotopic residual correction processes
HTML articles powered by AMS MathViewer

by V. Y. Pan, M. Kunin, R. E. Rosholt and H. Kodal PDF

Math. Comp. 75 (2006), 345-368 Request permission

Abstract:

We present and analyze homotopic (continuation) residual correction algorithms for the computation of matrix inverses. For complex indefinite Hermitian input matrices, our homotopic methods substantially accelerate the known nonhomotopic algorithms. Unlike the nonhomotopic case our algorithms require no pre-estimation of the smallest singular value of an input matrix. Furthermore, we guarantee rapid convergence to the inverses of well-conditioned structured matrices even where no good initial approximation is available. In particular we yield the inverse of a well-conditioned $n \times n$ matrix with a structure of Toeplitz/Hankel type in $O(n\log ^3n)$ flops. For a large class of input matrices, our methods can be extended to computing numerically the generalized inverses. Our numerical experiments confirm the validity of our analysis and the efficiency of the presented algorithms for well-conditioned input matrices and furnished us with the proper values of the parameters that define our algorithms.

References

James R. Bunch, Stability of methods for solving Toeplitz systems of equations, SIAM J. Sci. Statist. Comput. 6 (1985), no. 2, 349–364. MR 779410, DOI 10.1137/0906025
A. Ben-Israel, A Note on Iterative Method for Generalized Inversion of Matrices, Math. Comp., 20, 439–440, 1966.
Dario Andrea Bini and Beatrice Meini, Approximate displacement rank and applications, Structured matrices in mathematics, computer science, and engineering, II (Boulder, CO, 1999) Contemp. Math., vol. 281, Amer. Math. Soc., Providence, RI, 2001, pp. 215–232. MR 1855993, DOI 10.1090/conm/281/04659
J. Chun, T. Kailath, and H. Lev-Ari, Fast parallel algorithms for $QR$ and triangular factorization, SIAM J. Sci. Statist. Comput. 8 (1987), no. 6, 899–913. MR 911062, DOI 10.1137/0908073
Ioannis Z. Emiris, Victor Y. Pan, and Yanqiang Yu, Modular arithmetic for linear algebra computations in the real field, J. Symbolic Comput. 26 (1998), no. 1, 71–87. MR 1633585, DOI 10.1006/jsco.1998.0201
D. K. Faddeev and V. N. Faddeeva, Computational methods of linear algebra, W. H. Freeman and Co., San Francisco-London, 1963. Translated by Robert C. Williams. MR 0158519
Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
Georg Heinig and Frank Hellinger, On the Bezoutian structure of the Moore-Penrose inverses of Hankel matrices, SIAM J. Matrix Anal. Appl. 14 (1993), no. 3, 629–645. MR 1227768, DOI 10.1137/0614044
Georg Heinig and Frank Hellinger, Moore-Penrose inversion of square Toeplitz matrices, SIAM J. Matrix Anal. Appl. 15 (1994), no. 2, 418–450. MR 1266596, DOI 10.1137/S0895479892225853
Eugene Isaacson and Herbert Bishop Keller, Analysis of numerical methods, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR 0201039
Thomas Kailath, Sun Yuan Kung, and Martin Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), no. 2, 395–407. MR 533501, DOI 10.1016/0022-247X(79)90124-0
T. Kailath and A. H. Sayed (eds.), Fast reliable algorithms for matrices with structure, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. MR 1715813, DOI 10.1137/1.9781611971354
Victor Pan, On computations with dense structured matrices, Math. Comp. 55 (1990), no. 191, 179–190. MR 1023051, DOI 10.1090/S0025-5718-1990-1023051-7
Victor Pan, Parallel solution of Toeplitzlike linear systems, J. Complexity 8 (1992), no. 1, 1–21. MR 1153611, DOI 10.1016/0885-064X(92)90031-6
V. Y. Pan, Can We Utilize the Cancelation of the Most Significant Digits? Tech. Report TR-92-061, The International Computer Science Institute, Berkeley, California, 1992.
Victor Pan, Decreasing the displacement rank of a matrix, SIAM J. Matrix Anal. Appl. 14 (1993), no. 1, 118–121. MR 1199549, DOI 10.1137/0614010
Victor Y. Pan, Structured matrices and polynomials, Birkhäuser Boston, Inc., Boston, MA; Springer-Verlag, New York, 2001. Unified superfast algorithms. MR 1843842, DOI 10.1007/978-1-4612-0129-8
V. Y. Pan, A Homotopic Residual Correction Process, Proceedings of the Second Conference on Numerical Analysis and Applications (P. Yalamov, editor), Lecture Notes in Computer Science, 1988, 644–649, Springer, Berlin, 2001.
V. Y. Pan, A Homotopic/Factorization Process for Toeplitz-like Matrices with Newton’s/Conjugate Gradient Stages, Technical Report TR 2004014, Ph.D. Program in Computer Science, Graduate Center, City University of New York, New York, 2004.
Victor Y. Pan, Sheryl Branham, Rhys E. Rosholt, and Ai-Long Zheng, Newton’s iteration for structured matrices, Fast reliable algorithms for matrices with structure, SIAM, Philadelphia, PA, 1999, pp. 189–210. MR 1715820
V. Y. Pan, M. Kunin, R. Rosholt, H. Cebecioğlu, Residual Correction Algorithms for General and Structured Matrices, Technical Report TR 2002020, Ph.D. Program in Computer Science, Graduate Center, City University of New York, New York, 2002.
V. Y. Pan, B. Murphy, R. E. Rosholt, Y. Tang, X. Yan, Additive Preconditioning in Matrix Computations, Technical Report TR 2005009, Ph.D. Program in Computer Science, Graduate Center, City University of New York, New York, 2005.
V. Y. Pan, Y. Rami, Newton’s Iteration for the Inversion of Structured Matrices, Advances in the Theory of Computational Mathematics, Vol. 4: Structured Matrices: Recent Developments in Theory and Computation, (edited by D. A. Bini, E. Tyrtyshnikov and P. Yalamov), 79–90, Nova Science Publishers, Huntington, New York, 2001.
Victor Y. Pan, Youssef Rami, and Xinmao Wang, Structured matrices and Newton’s iteration: unified approach, Linear Algebra Appl. 343/344 (2002), 233–265. Special issue on structured and infinite systems of linear equations. MR 1878944, DOI 10.1016/S0024-3795(01)00336-6
Victor Pan and Robert Schreiber, An improved Newton iteration for the generalized inverse of a matrix, with applications, SIAM J. Sci. Statist. Comput. 12 (1991), no. 5, 1109–1130. MR 1114976, DOI 10.1137/0912058
Victor Y. Pan, Marc Van Barel, Xinmao Wang, and Gianni Codevico, Iterative inversion of structured matrices, Theoret. Comput. Sci. 315 (2004), no. 2-3, 581–592. MR 2073066, DOI 10.1016/j.tcs.2004.01.008
Victor Y. Pan and Xinmao Wang, Inversion of displacement operators, SIAM J. Matrix Anal. Appl. 24 (2003), no. 3, 660–677. MR 1972673, DOI 10.1137/S089547980238627X
Victor Y. Pan, Ailong Zheng, Xiaohan Huang, and Olen Dias, Newton’s iteration for inversion of Cauchy-like and other structured matrices, J. Complexity 13 (1997), no. 1, 108–124. MR 1449764, DOI 10.1006/jcom.1997.0431
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
G. Schultz, Iterative Berechnung der Reciproken Matrix, Z. Angew. Meth. Mech., 13, 57–59, 1933.
Torsten Söderström and G. W. Stewart, On the numerical properties of an iterative method for computing the Moore-Penrose generalized inverse, SIAM J. Numer. Anal. 11 (1974), 61–74. MR 341843, DOI 10.1137/0711008