Abstract
Hierarchical matrices (\({\mathcal{H}}\)-matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for \({\mathcal{H}}\)-matrices is almost optimal. In this paper we present an algebraic approach for constructing \({\mathcal{H}}\)-matrices which combines multilevel clustering methods with \({\mathcal{H}}\)-matrix arithmetic to compute the \({\mathcal{H}}\)-inverse, \({\mathcal{H}}\)-LU, and the \({\mathcal{H}}\) -Cholesky factors of a matrix. Then the \({\mathcal{H}}\)-inverse, \({\mathcal{H}}\)-LU or \({\mathcal{H}}\)-Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other \({\mathcal{H}}\)-matrix constructions based on Nested Dissection.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Börm, S., Grasedyck, L., Hackbusch, W.: Hierarchical matrices. Technical report, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig, Germany 2003. Lecture Notes No. 21. Available online at http://www.mis.mpg.de/preprints/ln/
S. Börm L. Grasedyck W. Hackbusch (2003) ArticleTitleIntroduction to hierarchical matrices with applications EABE 27 403–564
L. Grasedyck W. Hackbusch (2003) ArticleTitleConstruction and arithmetics of \({\mathcal{H}}\)-matrices Computing 70 IssueID4 295–334 Occurrence Handle1030.65033 Occurrence Handle10.1007/s00607-003-0019-1 Occurrence Handle2011419
W. Hackbusch (1999) ArticleTitleA sparse matrix arithmetic based on \({\mathcal{H}}\)-matrices. part i: Introduction to \({\mathcal{H}}\)-matrices Computing 62 89–108 Occurrence Handle0927.65063 Occurrence Handle10.1007/s006070050015 Occurrence Handle1694265
G. Karypis V. Kumar (1999) ArticleTitleA fast and high quality multilevel scheme for partitioning irregular graphs SIAM J. Sci. Comput. 20 IssueID1 359–392 Occurrence Handle0915.68129 Occurrence Handle10.1137/S1064827595287997 Occurrence Handle1639073
S. Le Borne L. Grasedyck (2006) ArticleTitle \({\mathcal{H}}\)-preconditioners in convection-dominated problems SIAM J. Matrix Anal. Appl. 27 IssueID4 1172–1183 Occurrence Handle1102.65051 Occurrence Handle10.1137/040615845 Occurrence Handle2205618
Le Borne, S., Grasedyck, L., Kriemann, R.: Domain-decomposition based \({\mathcal{H}}\)-LU preconditioners. In: Proc. 16th Int. Conf. on Domain Decomposition Methods (New York, 2005). Springer: LNCSE 2006 (forthcoming).
K. H. Leem S. Oliveira D. Stewart (2004) ArticleTitleAlgebraic multigrid (AMG) for saddle point systems from meshfree discretizations Numer. Linear Algebra Appl. 11 IssueID3 293–308 Occurrence Handle10.1002/nla.383 Occurrence Handle2065818
Persson, P., Strang, G.: A simple mesh generator in Matlab. SIAM Rev. 46(2) (2004).
Stewart, D. E., Leyk, Z.: Meschach: Matrix computations in C. Proc. CMA, vol. 32. The Australian National University 1994.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Oliveira, S., Yang, F. An algebraic approach for \({\mathcal{H}}\)-matrix preconditioners. Computing 80, 169–188 (2007). https://doi.org/10.1007/s00607-007-0224-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-007-0224-4