On the QR decomposition of backslashfancyscript H -matrices

Peter Benner, Thomas Mach

Research output: Contribution to journalArticle

Abstract

The hierarchical ( backslashfancyscriptH -) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix--matrix and matrix--vector products, matrix inversion and LU decomposition can be implemented efficiently using the backslashfancyscriptH -matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of backslashfancyscriptH -matrices. In the past, two different approaches for this task have been suggested in Bebendorf (Hierarchical matrices: a means to efficiently solve elliptic boundary value problems. Lecture notes in computational science and engineering (LNCSE), vol 63. Springer, Berlin, 2008) and Lintner (Dissertation, Fakultät für Mathematik, TU München. http://tumb1.biblio.tu-muenchen.de/publ/diss/ma/2002/lintner.pdf , 2002). We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an backslashfancyscriptH -matrix. Like other backslashfancyscriptH -arithmetic operations, the backslashfancyscriptH QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.
Original languageEnglish
Pages (from-to)111-129
Number of pages19
JournalComputing (Vienna/New York)
Volume88
Issue number3
DOIs
Publication statusPublished - Jun 9 2010

Fingerprint

QR Decomposition
H-matrix
Decomposition
Hierarchical Matrices
Linear Complexity
Linear algebra
Numerical Linear Algebra
LU decomposition
Computational Science
Sparse Data
Matrix Inversion
Cross product
Matrix Product
Least Squares Problem
Elliptic Boundary Value Problems
Engineering
Series
Boundary value problems

Cite this

On the QR decomposition of backslashfancyscript H -matrices. / Benner, Peter; Mach, Thomas.

In: Computing (Vienna/New York), Vol. 88, No. 3, 09.06.2010, p. 111-129.

Research output: Contribution to journalArticle

Benner, Peter ; Mach, Thomas. / On the QR decomposition of backslashfancyscript H -matrices. In: Computing (Vienna/New York). 2010 ; Vol. 88, No. 3. pp. 111-129.
@article{cec5d2c58a2e48dba1b4df78b48beb5f,
title = "On the QR decomposition of backslashfancyscript H -matrices",
abstract = "The hierarchical ( backslashfancyscriptH -) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix--matrix and matrix--vector products, matrix inversion and LU decomposition can be implemented efficiently using the backslashfancyscriptH -matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of backslashfancyscriptH -matrices. In the past, two different approaches for this task have been suggested in Bebendorf (Hierarchical matrices: a means to efficiently solve elliptic boundary value problems. Lecture notes in computational science and engineering (LNCSE), vol 63. Springer, Berlin, 2008) and Lintner (Dissertation, Fakult{\"a}t f{\"u}r Mathematik, TU M{\"u}nchen. http://tumb1.biblio.tu-muenchen.de/publ/diss/ma/2002/lintner.pdf , 2002). We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an backslashfancyscriptH -matrix. Like other backslashfancyscriptH -arithmetic operations, the backslashfancyscriptH QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.",
author = "Peter Benner and Thomas Mach",
year = "2010",
month = "6",
day = "9",
doi = "10.1007/s00607-010-0087-y",
language = "English",
volume = "88",
pages = "111--129",
journal = "Computing (Vienna/New York)",
issn = "0010-485X",
publisher = "Springer Wien",
number = "3",

}

TY - JOUR

T1 - On the QR decomposition of backslashfancyscript H -matrices

AU - Benner, Peter

AU - Mach, Thomas

PY - 2010/6/9

Y1 - 2010/6/9

N2 - The hierarchical ( backslashfancyscriptH -) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix--matrix and matrix--vector products, matrix inversion and LU decomposition can be implemented efficiently using the backslashfancyscriptH -matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of backslashfancyscriptH -matrices. In the past, two different approaches for this task have been suggested in Bebendorf (Hierarchical matrices: a means to efficiently solve elliptic boundary value problems. Lecture notes in computational science and engineering (LNCSE), vol 63. Springer, Berlin, 2008) and Lintner (Dissertation, Fakultät für Mathematik, TU München. http://tumb1.biblio.tu-muenchen.de/publ/diss/ma/2002/lintner.pdf , 2002). We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an backslashfancyscriptH -matrix. Like other backslashfancyscriptH -arithmetic operations, the backslashfancyscriptH QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.

AB - The hierarchical ( backslashfancyscriptH -) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix--matrix and matrix--vector products, matrix inversion and LU decomposition can be implemented efficiently using the backslashfancyscriptH -matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of backslashfancyscriptH -matrices. In the past, two different approaches for this task have been suggested in Bebendorf (Hierarchical matrices: a means to efficiently solve elliptic boundary value problems. Lecture notes in computational science and engineering (LNCSE), vol 63. Springer, Berlin, 2008) and Lintner (Dissertation, Fakultät für Mathematik, TU München. http://tumb1.biblio.tu-muenchen.de/publ/diss/ma/2002/lintner.pdf , 2002). We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an backslashfancyscriptH -matrix. Like other backslashfancyscriptH -arithmetic operations, the backslashfancyscriptH QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.

U2 - 10.1007/s00607-010-0087-y

DO - 10.1007/s00607-010-0087-y

M3 - Article

VL - 88

SP - 111

EP - 129

JO - Computing (Vienna/New York)

JF - Computing (Vienna/New York)

SN - 0010-485X

IS - 3

ER -