Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-13T19:51:55.452Z Has data issue: false hasContentIssue false
  • English
  • Français

An Inexact Shift-and-Invert Arnoldi Algorithm for Large Non-Hermitian Generalised Toeplitz Eigenproblems

Published online by Cambridge University Press:  28 May 2015

Ting-Ting Feng,
Gang Wu and
Ting-Ting Xu
Ting-Ting Feng
Affiliation:
School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou, 221116, Jiangsu, P.R. China
Gang Wu*
Affiliation:
School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou, 221116, Jiangsu, P.R. ChinaDepartment of Mathematics, China University of Mining and Technology, Xuzhou, 221116, Jiangsu, P.R. China
Ting-Ting Xu
Affiliation:
School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou, 221116, Jiangsu, P.R. China
*
*Corresponding author. Email addresses: tofengtingting@163.com (T.-T. Feng), gangwu76@126.com, wugangzy@gmail.com (G. Wu), xutingtingdream@163.com (T.-T. Xu)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The shift-and-invert Arnoldi method is a most effective approach to compute a few eigenpairs of a large non-Hermitian Toeplitz matrix pencil, where the Gohberg-Semencul formula can be used to obtain the Toeplitz inverse. However, two large non-Hermitian Toeplitz systems must be solved in the first step of this method, and the cost becomes prohibitive if the desired accuracy for this step is high — especially for some ill-conditioned problems. To overcome this difficulty, we establish a relationship between the errors in solving these systems and the residual of the Toeplitz eigenproblem. We consequently present a practical stopping criterion for their numerical solution, and propose an inexact shift-and-invert Arnoldi algorithm for the generalised Toeplitz eigenproblem. Numerical experiments illustrate our theoretical results and demonstrate the efficiency of the new algorithm.

Keywords

65F1565F10Toeplitz matrixgeneralised eigenproblemshift-and-invert Arnoldi methodGohberg-Semencul formula

Information

Type
Research Article
Information
East Asian Journal on Applied Mathematics , Volume 5 , Issue 2 , May 2015, pp. 160 - 175
Copyright
Copyright © Global-Science Press 2015 

References

[1]Alonso, P., Bernabeub, M., Garca, and Vidal, A., Implementation and tuning of a parallel symmetric Toeplitz eigensolver, J. Parallel Distrib. Comput. 71, 485–494 (2011).Google Scholar
[2]Bini, D. and Di Benedetto, F., Solving the generalised eigenvalue problem for rational Toeplitz matrices, SIAM J. Matrix Anal. Appl. 11, 537–552 (1990).Google Scholar
[3]Bogoya, J., Bottcher, A. and Grudsky, S., Asymptotics of individual eigenvalues of a class of large Hessenberg Toeplitz matrices. Operator Theory: Advances and Applications 220, 77–95 (2012).Google Scholar
[4]Chan, R. and Jin, X., An Introduction to Iterative Toeplitz Solvers, SIAM, Philadelphia (2007).Google Scholar
[5]Chan, R. and Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38, 427–482 (1996).Google Scholar
[6]Gohberg, I. and Semencul, A., On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled. 2, 201–233 (1972).Google Scholar
[7]Golub, G.H. and Van Loan, C.F., Matrix Computations, 4th edition, Johns Hopkins University Press (2012).Google Scholar
[8]Grudsky, S., Eigenvalues of larger Toeplitz matrices: The asymptotic approach, available from http://www.math.cinvestav.mx/~grudsky/talks.html (2010).Google Scholar
[9]Jia, Z. and Zhang, Y., A refined shift-and-invert Arnoldi algorithm for large unsymmetrix generalised eigenproblems, Comput. Math. Appl. 44, 1117–1127 (2002).CrossRefGoogle Scholar
[10]Kadanoff, L., Expansions for eigenfunctions and eigenvalues of large-n Toeplitz matrices, Papers in Physics 2, 020004 (2010).Google Scholar
[11]Lee, S., Pang, H. and Sun, H., Shift-invert Arnoldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput. 32, 774–792 (2010).CrossRefGoogle Scholar
[12]Mogan, R. and Zeng, M., A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Algebra Appl. 415. 96–113 (2006).Google Scholar
[13]Ng, M., Preconditioned Lanczos methods for the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Comput. 21, 1973–1986 (2000).CrossRefGoogle Scholar
[14]Ng, M., Iterative Methods for Toeplitz Systems, Oxford University Press (2004).Google Scholar
[15]Ng, M., Sun, H. and Jin, X., Recursive-based PCG methods for Toeplitz systems with nonnegative generating functions, SIAM J. Sci. Comput. 24, 1507–1529 (2003).CrossRefGoogle Scholar
[16]Oudin, M. and Delmas, J., Asymptotic generalised eigenvalue distribution of block multilevel Toeplitz matrices, IEEE Tran. Signal Processing 57. 382–387 (2009).CrossRefGoogle Scholar
[17]Pang, H. and Sun, H., Shift-Invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential, Numer. Linear Algebra Appl. 18, 603–614 (2011).CrossRefGoogle Scholar
[18]Parlett, B.N. and Saad, Y., Complex shift and invert strategies for real matrices, Linear Algebra Appl. 88/89, 575–595 (1987).CrossRefGoogle Scholar
[19]Saad, Y., Numerical Methods for Large Eigenvalues Problems, 2nd edition, SIAM, Philadelphia (2011).CrossRefGoogle Scholar
[20]Sorensen, D., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13, 357–385 (1992).CrossRefGoogle Scholar
[21]Vidal, A., Garcia, V.Alonso, P. and Bernabeu, M., Parallel computation of the eigenvalues of symmetric Toeplitz matrices through iterative methods, J. Parallel Distrib. Comput. 68, 1113–1121 (2008).Google Scholar
[22]Wang, Y. and Lu, L., Preconditioned Lanczos method for generalised Toeplitz eigenvalue problems, J. Comput. Appl. Math. 226, 66–76 (2009).Google Scholar
[23]Wu, G., Feng, T. and Wei, Y., An inexact shift-and-invert Arnoldi algorithm for Toeplitz matrix exponential, Numer. Linear Algebra Appl., accepted.Google Scholar
[24]Wu, K. and Simon, H., Thick-restart Lanczos method for large symmetric eigenvalue problems, SIAM J. Matrix Anal. Appl. 22, 602–616 (2000).CrossRefGoogle Scholar
[25]Zhang, L., Liu, W. and Peng, B., Generalised eigenvector problem for Hermitian Toeplitz matrices and its application to beamforming, Signal Proc. 92, 374–380 (2012).Google Scholar