Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T08:37:03.276Z Has data issue: false hasContentIssue false
  • English
  • Français

Superoptimal Preconditioners for Functions of Matrices

Part of: Partial differential equations, boundary value problems Numerical analysis: Ordinary differential equations Numerical linear algebra

Published online by Cambridge University Press:  10 November 2015

Zheng-Jian Bai ,
Xiao-Qing Jin  and
Teng-Teng Yao
Zheng-Jian Bai*
Affiliation:
School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
Xiao-Qing Jin
Affiliation:
Department of Mathematics, University of Macau, Macao, P. R. China
Teng-Teng Yao
Affiliation:
School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
*
*Corresponding author. Email address: [email protected](Z. J. Bai), [email protected](X. Q. Jin), [email protected] (T. T. Yao)
Get access

Abstract

For any given matrix A ∈ℂnxn, a preconditioner tU(A) called the superoptimal preconditioner was proposed in 1992 by Tyrtyshnikov. It has been shown that tU(A) is an efficient preconditioner for solving various structured systems, for instance, Toeplitz-like systems. In this paper, we construct the superoptimal preconditioners for different functions of matrices. Let f be a function of matrices from ℂnxn to ℂnxn. For any A ∈ ℂ nxn, one may construct two superoptimal preconditioners for f(A): tU(f(A)) and f(tU(A)). We establish basic properties of tU(f(A)) and f(tU(A)) for different functions of matrices. Some numerical tests demonstrate that the proposed preconditioners are very efficient for solving the system f(A)x = b.

Keywords

Superoptimal preconditionersfunctions of matricesToeplitz matrixPCG method

MSC classification

Secondary: 65F10: Iterative methods for linear systems 65F15: Eigenvalues, eigenvectors 65L05: Initial value problems 65N22: Solution of discretized equations
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 8 , Issue 4 , November 2015 , pp. 515 - 529
Copyright
Copyright © Global-Science Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Baker, A., Matrix Groups -An Introduction to Lie Group Theory, Springer, New York, 2002.Google Scholar
[2]Di Benedetto, F., Estatico, C., and Serra-Capizzano, S., Superoptimal preconditioner conjugate gradient iteration for image deblurring, SIAM J. Sci. Comput., vol. 26 (2005), pp.1012–1035.CrossRefGoogle Scholar
[3]Bernstein, D., Matrix Mathematics - Theory, Facts, and Formulas, Princeton University Press, Princeton, 2009.CrossRefGoogle Scholar
[4]Chan, R. and Jin, X., An Introduction to Iterative Toeplitz Solvers, SIAM, Philadelpha, 2007.CrossRefGoogle Scholar
[5]Chan, R., Jin, X., and Yeung, M., The circulant operator in the Banach algebra of matrices, Linear Algebra Appl., vol. 149 (1991), pp. 41–53.CrossRefGoogle Scholar
[6]Chan, R., Jin, X., and Yeung, M., The spectra of super-optimal circulant preconditioned Toeplitz systems, SIAM J. Numer Anal., vol. 28 (1991), pp. 871–879.CrossRefGoogle Scholar
[7]Chan, R. and Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Review, vol. 38 (1996), pp. 427–482.CrossRefGoogle Scholar
[8]Chan, T., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., vol. 9 (1988), pp. 766–771.CrossRefGoogle Scholar
[9]Cheng, C., Jin, X., Vong, S., and Wang, W., A note on spectra of optimal and superoptimal preconditioned matrices, Linear Algebra Appl., vol. 422 (2007), pp. 482–485.CrossRefGoogle Scholar
[10]Cheng, C., Jin, X. and Wei, Y., Stability properties of superoptimal preconditioner from numerical range, Numer. Linear Algebra Appl., vol. 13 (2006), pp. 513–521.CrossRefGoogle Scholar
[11]Estatico, C., A class of filtering superoptimal preconditioners for highly ill conditioned linear systems, BIT, vol. 42 (2002), pp. 753–778.CrossRefGoogle Scholar
[12]Higham, N., Functions of Matrices - Theory and Computation, SIAM, Philadelpha, 2008.CrossRefGoogle Scholar
[13]Jin, X., Preconditioning Techniques for Toeplitz Systems, Higher Education Press, Beijing, 2010.Google Scholar
[14]Jin, X. and Wei, Y., A short note on singular values of optimal and superoptimal preconditioned matrices, International J. Comput. Math. vol. 84 (2007), pp. 1261–1263.CrossRefGoogle Scholar
[15]Jin, X. and Wei, Y., A survey and some extensions ofT Chan's preconditioner, Linear Algebra Appl., vol. 428 (2008), pp. 403–412.CrossRefGoogle Scholar
[16]Jin, X., Zhao, Z., and Tam, S., Optimal preconditioners for functions of matrices, Linear Algebra Appl., vol. 457 (2014), pp. 224–243.CrossRefGoogle Scholar
[17]Lee, S., Liu, X., and Sun, H., Fast exponential time integration scheme for option pricing with jumps, Numer. Linear Algebra Appl., vol. 19 (2012), pp. 87–101.CrossRefGoogle Scholar
[18]Lee, S., Pang, H., and Sun, H., Shift-invert Aronldi approximation to the Toeplitz matrix exponential, SIAM J. Sci. Comput., vol. 32 (2010), pp. 774–792.CrossRefGoogle Scholar
[19]Moler, C. and Van Loan, C., Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Review, vol. 45 (2003), pp. 3–49.CrossRefGoogle Scholar
[20]Tyrtyshnikov, E., Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl., vol. 13 (1992), pp. 459–473.CrossRefGoogle Scholar