Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

Simultaneous iterative reduction of large sparse matrix pairs with shift-and-invert Lanczos and Arnoldi methods

DOI: http://dx.doi.org/10.15439/2026F9644

Citation: Roger B. Sidje (). Simultaneous iterative reduction of large sparse matrix pairs with shift-and-invert Lanczos and Arnoldi methods. In M. Bolanowski, M. Ganzha, M. Grzegorowski, L. Maciaszek, M. Paprzycki, A. Paszkiewicz, D. Ślęzak (eds), Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS). ACSIS, Vol. 47, pages 397–410.

Full text

Abstract. We describe iterative methods for simultaneously reducing large sparse matrix pairs using congruence transformations. For a symmetric pair, the reduction is tridiagonal-tridiagonal, while it is Hessenberg-Hessenberg for a nonsymmetric pair. We show how these reduction schemes relate to the well-established shift-and-invert Lanczos and Arnoldi methods when initialized with suitably chosen starting vectors, thus revealing capabilities that had so far remained obscured and untapped. In the setting of solving the generalized eigenvalue problem, we show how the tridiagonal-tridiagonal form further simplifies to tridiagonal-diagonal at no extra cost, and the Hessenberg-Hessenberg form to Hessenberg-triangular at no extra cost too. Illustrative numerical results are given.

References

  1. S. D. Garvey, F. Tisseur, M. I. Friswell, J. E. T. Penny, and U. Prells, “Simultaneous tridiagonalization of two symmetric matrices,” Int. J. Numer. Meth. Engng, vol. 57, no. 12, pp. 1643–1660, 2003. https://doi.org/10.1002/nme.733
  2. R. B. Sidje, “On the simultaneous tridiagonalization of two symmetric matrices,” Numer. Math., vol. 118, no. 3, pp. 549–566, 2011. https://doi.org/10.1007/s00211-010-0357-9
  3. F. Tisseur, “Tridiagonal-diagonal reduction of symmetric indefinite pairs,” SIAM J. Matrix Anal. Appl., vol. 26, no. 1, pp. 215–232, 2004. https://doi.org/10.1137/S0895479802414783
  4. B. Nour-Omid, B. N. Parlett, T. Ericsson, and P. S. Jensen, “How to implement the spectral transformation,” Math. Comp., vol. 48, pp. 663– 673, 1987. https://doi.org/10.1090/s0025-5718-1987-0878698-5
  5. Y. Saad, Numerical Methods for Large Eigenvalue Problems. Society for Industrial and Applied Mathematics, 2011, https://doi.org/10. 1137/1.9781611970739.
  6. T. Ericsson and A. Ruhe, “The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems,” Math. Comp., vol. 35, no. 152, pp. 1251–1268, 1980. https://doi.org/10.2307/2006390
  7. D. C. Sorensen, “Truncated QZ methods for large scale generalized eigenvalue problems,” ETNA, vol. 7, pp. 141–162, 1998. [Online]. Available: https://eudml.org/doc/119806
  8. R.-C. Li and Q. Ye, “Simultaneous similarity reductions for a pair of matrices to condensed forms,” Commun. Math. Stat., vol. 2, no. 2, pp. 139–153, 2014. https://doi.org/10.1007/s40304-014-0033-y
  9. M. L. Parks, E. de Sturler, G. Mackey, D. D. Johnson, and S. Maiti, “Recycling Krylov subspaces for sequences of linear systems,” SIAM J. Sci. Comput., vol. 28, no. 5, p. 1651–1674, Sep. 2006. https://doi.org/10.1137/040607277
  10. B. N. Parlett, “A new look at the Lanczos algorithm for solving symmetric systems of linear equations,” Linear Algebra Appl., vol. 29, pp. 323 – 346, 1980. https://doi.org/10.1016/0024-3795(80)90248-7
  11. Y. Saad, “On the Lanczos method for solving symmetric linear systems with several right-hand sides,” Math. Comp., vol. 48, pp. 651–662, 1987. https://doi.org/10.2307/2007834
  12. B. N. Parlett and H. C. Chen, “Use of indefinite pencils for computing damped natural modes,” Linear Algebra Appl., vol. 140, pp. 53–88, 1990. https://doi.org/10.1016/0024-3795(90)90222-X
  13. G. H. Golub and Q. Ye, “An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems,” SIAM J. Sci. Comput., vol. 24, no. 1, pp. 312–334, 2002. https://doi.org/10.1137/S1064827500382579
  14. G. L. G. Sleijpen, A. G. L. Booten, D. R. Fokkema, and H. A. van der Vorst, “Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems,” BIT Num. Math., vol. 36, no. 3, pp. 595–633, 1996. https://doi.org/10.1007/BF01731936
  15. M. A. Freitag, A. Spence, and E. Vainikko, “Rayleigh quotient iteration and simplified Jacobi-Davidson with preconditioned iterative solves for generalised eigenvalue problems,” Department of Mathematics, University of Bath, Bath, UK, Tech. Rep., 2008.
  16. D. B. Szyld and F. Xue, “Efficient preconditioned inner solves for inexact Rayleigh quotient iteration and their connections to the singlevector Jacobi-Davidson method,” SIAM J. Mat. Anal. Appl., vol. 32, pp. 993–1018, 2011. https://doi.org/10.1137/100807922 F. Tisseur and K. Meerbergen, “The quadratic eigenvalue problem,” SIAM Review, vol. 43, no. 2, pp. 235–286, 2001. https://doi.org/10.1137/S0036144500381988
  17. R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge University Press, 2012, https://doi.org/10.1017/CBO9780511810817.
  18. Z. Bai, “Krylov subspace techniques for reduced-order modeling of large-scale dynamical systems,” Appl. Num. Math., vol. 43, no. 1, pp. 9–44, 2002. https://doi.org/10.1016/S0168-9274(02)00116-2
  19. Y. Chahlaoui, K. A. Gallivan, A. Vandendorpe, and P. Van Dooren, “Model reduction of second-order systems,” in Dimension Reduction of Large-Scale Systems, P. Benner, D. C. Sorensen, and V. Mehrmann, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. https://doi.org/10.1007/3-540-27909-1. ISBN 978-3-540-27909-9 pp. 149–172.
  20. K. Gallivan, G. Grimme, and P. Van Dooren, “A rational Lanczos algorithm for model reduction,” Numer. Algorithms, vol. 12, no. 1, pp. 33–63, 1996. https://doi.org/10.1007/BF02141740
  21. B. N. Parlett, D. R. Taylor, and Z. A. Liu, “A look ahead Lanczos algorithm for unsymmetric matrices,” Math. Comp., vol. 44, pp. 105– 124, 1985. https://doi.org/10.2307/2007796
  22. Y. Saad, “The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems,” SIAM J. Numer. Anal., vol. 19, no. 3, pp. 485–506, 1982. https://doi.org/10.1137/0719031
  23. W. Joubert, “Lanczos methods for the solution of nonsymmetric systems of linear equations,” SIAM J. Mat. Anal. Appl., vol. 13, no. 3, pp. 926– 943, 1992. https://doi.org/10.1137/0613056
  24. M. A. Brebner and J. Grad, “Eigenvalues of Ax = λBx for real symmetric matrices A and B computed by reduction to a pseudosymmetric form and the HR process,” Linear Algebra Appl., vol. 43, pp. 99–118, 1982. https://doi.org/10.1016/0024-3795(82)90246-4
  25. D. Bini, L. Gemignani, and F. Tisseur, “The Ehrlich–Aberth method for the nonsymmetric tridiagonal eigenvalue problem,” SIAM J. Mat. Anal. Appl., vol. 27, no. 1, pp. 153–175, 2005. https://doi.org/10.1137/S0895479803429788
  26. G. H. Golub and C. F. Van Loan, Matrix Computations 4th Edition. Philadelphia, PA: Johns Hopkins University Press, 2013, https://dx.doi.org/10.1137/1.9781421407944. [Online]. Available: https: //epubs.siam.org/doi/abs/10.1137/1.9781421407944
  27. F. De Terán, “Canonical forms for congruence of matrices and Tpalindromic matrix pencils: a tribute to H. W. Turnbull and A. C. Aitken,” SeMA Journal, vol. 73, no. 1, pp. 7–16, 2016. https://doi.org/10.1007/s40324-015-0052-y
  28. I. S. Duff, R. G. Grimes, and J. G. Lewis, “Sparse matrix test problems,” ACM Trans. Math. Software, vol. 15, no. 1, pp. 1–14, 1989. https://doi.org/10.1145/62038.62043
  29. Z. Bai, D. Day, J. W. Demmel, and J. J. Dongarra, “A test matrix collection for non-Hermitian eigenvalue problems (release 1.0),” Department of Computer Science, University of Tennessee, Knoxville, TN, USA, LAPACK Working Note 123, Tech. Rep. UT-CS-97-355, Mar. 1997. [Online]. Available: http://www.netlib.org/lapack/lawnspdf/ lawn123.pdf