×

zbMATH — the first resource for mathematics

Additive preconditioning, eigenspaces, and the inverse iteration. (English) Zbl 1159.65043
In modern eigensolvers such as the inverse power method, the Jacobi-Davidson algorithm, and the Arnoldi iteration with shift-and-invert technique the iteration requires the solution of a system of linear algebraic equations for every loop. Because the systems are prevalently ill-conditioned in general factorizations of the input matrix have to be used to overcome accuracy and iteration number problems in the inverse iteration. The ill-conditioning of the matrix is especially a disadvantage in the case of large-scale problems that need the application of iterative algorithms for the solution of the linear systems.
The main feature of the paper consists in the application of an additive randomized preconditioning technique, already developed in the previous paper by V. Y. Pan, D. Ivolgin, B. Morphy, R. E. Rosholt, Y. Tang and X. Yan [Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 5010, 372–383 (2008; Zbl 1142.68607)] to the systems to improve the conditioning of the input matrix and subsequently to reduce the iteration number and to increase the accuracy in the inverse iteration covering also the cases of multiple and clustered eigenvalues. It is proved that the quadratic convergence of the inverse method is preserved. The fast global convergence is claimed by experiments. The results are verified by numerical examples of small matrix order (\(n = 64\), \(n = 100\)).

MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Greenbaum, A., Iterative methods for solving linear systems, (1997), SIAM Philadelphia · Zbl 0883.65022
[2] Benzi, M., Preconditioning techniques for large linear systems: a survey, J. comput. phys., 182, 418-477, (2002) · Zbl 1015.65018
[3] Chen, K., Matrix preconditioning techniques and applications, (2005), Cambridge University Press Cambridge, England · Zbl 1079.65057
[4] Golub, G.H.; Van Loan, C.F., Matrix computations, (1996), The Johns Hopkins University Press Baltimore, Maryland · Zbl 0865.65009
[5] Pan, V.Y.; Ivolgin, D.; Murphy, B.; Rosholt, R.E.; Taj-Eddin, I.; Tang, Y.; Yan, X., Additive preconditioning and aggregation in matrix computations, Comput. math. appl., 55, 8, 1870-1886, (2008) · Zbl 1139.65034
[6] V.Y. Pan, D. Ivolgin, B. Murphy, R.E. Rosholt, Y. Tang, X. Yan, Additive preconditioning for matrix computations, Technical Report TR 2008004, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2008. <http://www.cs.gc.cuny.edu/tr/techreport.php?id=352>. · Zbl 1142.68607
[7] V.Y. Pan, D. Ivolgin, B. Murphy, R.E. Rosholt, Y. Tang, X. Yan, Additive preconditioning for matrix computations, in: Proceedings of the Third International Computer Science Symposium in Russia (CSR 2008), Lecture Notes in Computer Science (LNCS), vol. 5010, 2008, pp. 372-383. · Zbl 1142.68607
[8] Trefethen, L.N.; Bau, D., Numerical linear algebra, (1997), SIAM Philadelphia · Zbl 0874.65013
[9] Barrett, R.; Berry, M.W.; Chan, T.F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., Templates for the solution of linear systems: building blocks for iterative methods, (1993), SIAM Philadelphia · Zbl 0814.65030
[10] Saad, Y., Iterative methods for sparse linear systems, (1996), PWS Publishing Co. Boston, SIAM Publications, Philadelphia, second ed., 2003 · Zbl 1002.65042
[11] van der Vorst, H.A., Iterative Krylov methods for large linear systems, (2003), Cambridge University Press Cambridge, England · Zbl 1023.65027
[12] V.Y. Pan, Univariate polynomial root-finding with lower precision and higher convergence rate, Technical Report TR 2002003, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2002. <http://www.cs.gc.cuny.edu/tr/techreport.php?id=352>.
[13] D.A. Bini, L. Gemignani, V.Y. Pan, Inverse power and Durand/Kerner iteration for univariate polynomial root-finding, Comput. Math. Appl. 47(2-3) (2004) 447-459 (also Technical Report TR 2002020, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2002. <http://www.cs.gc.cuny.edu/tr/techreport.php?id=352>). · Zbl 1054.65046
[14] Wilkinson, J.H., The algebraic eigenvalue problem, (1965), Clarendon Press Oxford · Zbl 0258.65037
[15] Ipsen, I.C.F., Computing an eigenvector with inverse iteration, SIAM rev., 39, 354-391, (1998)
[16] Chu, M.T.; Funderlic, R.E.; Golub, G.H., A rank-one reduction formula and its applications to matrix factorizations, SIAM rev., 37, 4, 512-530, (1995) · Zbl 0844.65033
[17] Hubert, L.; Meulman, J.; Heiser, W., Two purposes for matrix factorization: a historical appraisal, SIAM rev., 42, 1, 68-82, (2000) · Zbl 0999.65014
[18] Golub, G.H., Some modified matrix eigenvalue problems, SIAM rev., 15, 318-334, (1973) · Zbl 0254.65027
[19] Bini, D.; Pan, V.Y., Computing matrix eigenvalues and polynomial zeros where the output is real, SIAM J. comput., 27, 4, 1099-1115, (1998), (Proceedings version in Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’91), ACM Press, New York, and SIAM Publications, Philadelphia, 1991, pp. 384-393) · Zbl 0911.68050
[20] Stewart, G.W., Matrix algorithms, Eigensystems, vol. II, (1998), SIAM Philadelphia, second ed., 2001
[21] Jessup, E.R., A case against a divide and conquer approach to the nonsymmetric eigenvalue problem, Appl. numer. math., 12, 403-420, (1993) · Zbl 0782.65052
[22] V.Y. Pan, Computations in the null spaces with additive preconditioning, Technical Report TR 2007009, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2007. <http://www.cs.gc.cuny.edu/tr/techreport.php?id=352>.
[23] V.Y. Pan, G. Qian, Solving homogeneous linear systems with weakly randomized additive preprocessing, Technical Report TR 2008009, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2008. <http://www.cs.gc.cuny.edu/tr/techreport.php?id=352>.
[24] Pan, V.Y.; Yan, X., Null space and eigenspace computations with additive preprocessing, (), 152-160
[25] Stewart, G.W., Matrix algorithms, Basic decompositions, vol. I, (1998), SIAM Philadelphia · Zbl 0910.65012
[26] Demmel, J.W., Applied numerical linear algebra, (1997), SIAM Philadelphia · Zbl 0879.65017
[27] Higham, N.J., Accuracy and stability in numerical analysis, (2002), SIAM Philadelphia
[28] ()
[29] Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, New Jersey, SIAM, Philadelphia, 1998 · Zbl 0431.65016
[30] Wilkinson, J.H., Global convergence of tridiagonal QR algorithm with origin shifts, Linear algebra appl., 1, 409-420, (1968) · Zbl 0237.65029
[31] V.Y. Pan, The Schur aggregation and extended iterative refinement, Technical Report TR 2007, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2007.
[32] Pan, V.Y.; Murphy, B.; Rosholt, R.E.; Tabanjeh, M., The Schur aggregation for solving linear systems of equations, (), 142-151
[33] V.Y. Pan, D. Grady, B. Murphy, G. Qian, R.E. Rosholt, A. Ruslanov, Schur aggregation for linear systems and determinants, in: D.A. Bini, V.Y. Pan, J. Verschelde (Eds.), Theoretical Computer Science, Special Issue on Symbolic-Numerical Algorithms. Also Technical Report TR 2008008, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2008. <http://www.cs.gc.cuny.edu/tr/techreport.php?id=352>. · Zbl 1159.65046
[34] Demillo, R.A.; Lipton, R.J., A probabilistic remark on algebraic program testing, Inform. process. lett., 7, 4, 193-195, (1978) · Zbl 0397.68011
[35] Zippel, R.E., Probabilistic algorithms for sparse polynomials, (), 216-226
[36] Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701-717, (1980) · Zbl 0452.68050
[37] Pan, V.Y., Solving a polynomial equation: some history and recent progress, SIAM rev., 39, 2, 187-220, (1997) · Zbl 0873.65050
[38] Malek, F.; Vaillancourt, R., Polynomial zerofinding iterative matrix algorithms, Comput. math. appl., 29, 1, 1-13, (1995) · Zbl 0812.65039
[39] Malek, F.; Vaillancourt, R., A composite polynomial zerofinding matrix algorithm, Comput. math. appl., 30, 2, 37-47, (1995) · Zbl 0846.65021
[40] Fortune, S., An iterated eigenvalue algorithm for approximating roots of univariate polynomials, J. symbol. comput., 33, 5, 627-646, (2002), Proc. version in Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’01), ACM Press, New York, 2001, pp. 121-128 · Zbl 1004.65060
[41] D.A. Bini, L. Gemignani, V.Y. Pan, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equation, Numer. Math. 3 (2005) 373-408 (also Technical Report 1470, Department of Math., University of Pisa, Pisa, Italy, July 2003). · Zbl 1072.65068
[42] Bini, D.A.; Gemignani, L.; Pan, V.Y., Improved initialization of the accelerated and robust QR-like polynomial root-finding, Electron. trans. numer. anal., 17, 195-205, (2004) · Zbl 1065.65065
[43] Pan, V.Y.; Ivolgin, D.; Murphy, B.; Rosholt, R.E.; Tang, Y.; Wang, X.; Yan, X., Root-finding with eigen-solving, (), 219-245
[44] Pan, V.Y., Amended dsesc power method for polynomial root-finding, Comput. math. appl., 49, 9-10, 1515-1524, (2005) · Zbl 1077.65049
[45] Wilkinson, J.H., Note on matrices with a very ill-conditioned eigenproblem, Numer. math., 19, 176-178, (1972) · Zbl 0252.65027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.