• Contents V46
• Online Suppl
• CTAC 2004
• Part 1
• Part 2
• Part 3
• Part 4
• Author index
• Journal home
• RSS News
• Information
• for Readers
• for Authors
• for Referees
• Other e-journals
• Aust Math Soc
• 
  

ANZIAM J. 46(E) ppC472--C487, 2005.

Approximating functions of a large sparse positive definite matrix using a spectral splitting method

M. Ilic

I. W. Turner

(Received 21 October 2004, revised 1 May 2005)

Abstract

The computation of functions of large sparse matrices f(A) is an important topic in numerical linear algebra and finds application in many fields of applied mathematics and statistics. In previous research we considered SPD matrices with compact spectrum s(A) Ì [a,b] and proposed low degree matrix polynomial approximations p( A) such that e = ||f( A) - p( A ) || was small on the spectral interval, where the extreme eigenvalues a and b were calculated using Krylov subspace approximation. For the class of matrices examined, the thick restarted Lanczos scheme enabled rapid convergence to the extreme eigenvalues and these Ritz values were used to construct cubic near-minimax Chebyshev least squares approximations of the desired matrix functions. There is a good balance between accuracy and efficiency for this approximation method. The aim of the present study is to extend the previously developed matrix function approximation technique to enable SPD matrices with a wider spectrum to be treated using a novel splitting of s(A). In this case, the decomposition of f(A) as a sum of a 'singular' part and a 'regular' part is investigated. To perform the split a projector onto the singular part is here constructed using Krylov subspace approximation. Numerical results for a representative large sparse positive definite matrix appear promising.

Download to your computer

• Click here for the PDF article (214 kbytes) We suggest printing 2up.
• Click here for its BiBTeX record

Authors

M. Ilic

I. W. Turner

School of Mathematical Sciences, Queensland University of Technology, Australia mailto:i.turner@qut.edu.au

Published June 9, 2005. ISSN 1446-8735

References

1. K. E. Atkinson. An introduction to Numerical Analysis second edition, Wiley, 1989.
2. Z. Bai, M. Fahey and G. Golub. Some large-scale matrix computation problems, J. Computational and Applied Maths, 74, pp.71--89, 1996.
3. Z. Battles and L. N. Trefethen, An extension of MATLAB to continuous functions and operators. Oxford University Computing Laboratory, Numerical Analysis Group, Report 03/03, 2003.
4. S. Cheng, N. Higham, C. S. Kenney and A. Laub. Approximating the logorithm of a matrix to specified accuracy. SIAM J. Matrix Analysis and Applications, 22, 4, pp.1112--1125, 2001.
5. V. L. Druskin and L. A. Knizhnerman. Krylov subspace approximations of eigenpairs and matrix functions in exact and computer arithmetic. Numerical Linear Algebra with Applications, 2:205--217, 1995.
6. J. Erhel, K. Burrage and B. Pohl. Restarted GMRES Preconditioned by Deflation, J. Comput. Appl. Math, 69, pp.303--318, 1996.
7. M. Hochbruck and C. Lubich. On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numerical Analysis, 34, pp.1911--1925, 1997.
8. M. Ilic and I. W. Turner, Krylov Subspaces and the Analytic Grade, J. Numerical Linear Algebra with Applications, published online 17 June, 2004.
9. M. Ilic, I. W. Turner and A. N. Pettitt, Bayesian Computations and Efficient Algorithms for Computing Functions of Large, Sparse Matrices, Proceedings of the Biennial Computation Techniques and Applications Conference --- CTAC 2003, ANZIAM J. 45 (E) pp.C504--C518, 2004.
10. A. Ruhe. Lanczos Method (Section 4.4). In Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. van der Vorst, editors, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia, 2000.
11. Y. Saad. Iterative Methods for Sparse Linear Systems, SIAM, 2002. Approximation, Prentice Hall, Englewood Cliffs, New Jersey USA, 1996.
12. A. Stathopoulos, Y. Saad, and K. Wu. Dynamic Thick Restarting of the Davidson, and the Implicitly Restarted Arnoldi Methods, SIAM J. Scientific Computing. (19:1) pp.229--245, 1998.
13. H. A. van der Vorst. An iterative solution method for solving f(A)x=b using Krylov subspace information obtained for the symmetric positive definite matrix A, J. Computational and Applied Mathematics, 18, 249--263, 1987.