Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-15T20:22:30.785Z Has data issue: false hasContentIssue false
  • English
  • Français

Superoptimal Preconditioners for Functions of Matrices

Part of:Numerical analysis: Ordinary differential equationsPartial differential equations, boundary value problemsNumerical 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. Emailaddress: zjbai@xmu.edu.cn(Z. J.Bai), xqjin@umac.mo(X. Q. Jin),yaotengteng718@163.com (T.T. Yao)

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.

For any given matrix A ∈ℂnxn, a preconditioner tU(A) called thesuperoptimal preconditioner was proposed in 1992 by Tyrtyshnikov. It has beenshown that tU(A) is an efficient preconditioner forsolving various structured systems, for instance, Toeplitz-like systems. In thispaper, we construct the superoptimal preconditioners for different functions ofmatrices. 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)) andf(tU(A)) for different functions ofmatrices. Some numerical tests demonstrate that the proposed preconditioners arevery efficient for solving the system f(A)x = b.

Keywords

Superoptimal preconditionersfunctions of matricesToeplitz matrixPCG method

MSC classification

Secondary:65F10: Iterative methods for linear systems65F15: Eigenvalues, eigenvectors65L05: Initial value problems65N22: Solution of discretized equations

Information

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 

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