The LR Cholesky algorithm for symmetric hierarchical matrices

Peter Benner, Thomas Mach

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We investigate the application of the LR Cholesky algorithm to symmetric hierarchical matrices, symmetric simple structured hierarchical matrices and symmetric hierarchically semiseparable (HSS) matrices. The data-sparsity of these matrices make the otherwise expensive LR Cholesky algorithm applicable, as long as the data-sparsity is preserved. We will see in an example that the ranks of the low rank blocks grow and the data-sparsity gets lost. We will explain this behavior by applying a theorem on the structure preservation of diagonal plus semiseparable matrices under LR Cholesky transformations. Therefore we have to give a new more constructive proof for the theorem. We will show that the structure of Hℓ-matrices is almost preserved and so the LR Cholesky algorithm is of almost quadratic complexity for Hℓ-matrices.

Original languageEnglish
Pages (from-to)1150-1166
Number of pages17
JournalLinear Algebra and Its Applications
Volume439
Issue number4
DOIs
Publication statusPublished - 2013
Externally publishedYes

Fingerprint

Hierarchical Matrices
Cholesky
Symmetric matrix
Semiseparable Matrices
Sparsity
H-matrix
Structured Matrices
Theorem
Preservation

Keywords

  • Eigenvalues
  • Hℓ-Matrices
  • LR Cholesky algorithm
  • Semiseparable matrices
  • Symmetric hierarchical matrices

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this

The LR Cholesky algorithm for symmetric hierarchical matrices. / Benner, Peter; Mach, Thomas.

In: Linear Algebra and Its Applications, Vol. 439, No. 4, 2013, p. 1150-1166.

Research output: Contribution to journalArticle

Benner, Peter ; Mach, Thomas. / The LR Cholesky algorithm for symmetric hierarchical matrices. In: Linear Algebra and Its Applications. 2013 ; Vol. 439, No. 4. pp. 1150-1166.
@article{f4695a043e9046a58b673a5c93246f05,
title = "The LR Cholesky algorithm for symmetric hierarchical matrices",
abstract = "We investigate the application of the LR Cholesky algorithm to symmetric hierarchical matrices, symmetric simple structured hierarchical matrices and symmetric hierarchically semiseparable (HSS) matrices. The data-sparsity of these matrices make the otherwise expensive LR Cholesky algorithm applicable, as long as the data-sparsity is preserved. We will see in an example that the ranks of the low rank blocks grow and the data-sparsity gets lost. We will explain this behavior by applying a theorem on the structure preservation of diagonal plus semiseparable matrices under LR Cholesky transformations. Therefore we have to give a new more constructive proof for the theorem. We will show that the structure of Hℓ-matrices is almost preserved and so the LR Cholesky algorithm is of almost quadratic complexity for Hℓ-matrices.",
keywords = "Eigenvalues, Hℓ-Matrices, LR Cholesky algorithm, Semiseparable matrices, Symmetric hierarchical matrices",
author = "Peter Benner and Thomas Mach",
year = "2013",
doi = "10.1016/j.laa.2013.03.001",
language = "English",
volume = "439",
pages = "1150--1166",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier",
number = "4",

}

TY - JOUR

T1 - The LR Cholesky algorithm for symmetric hierarchical matrices

AU - Benner, Peter

AU - Mach, Thomas

PY - 2013

Y1 - 2013

N2 - We investigate the application of the LR Cholesky algorithm to symmetric hierarchical matrices, symmetric simple structured hierarchical matrices and symmetric hierarchically semiseparable (HSS) matrices. The data-sparsity of these matrices make the otherwise expensive LR Cholesky algorithm applicable, as long as the data-sparsity is preserved. We will see in an example that the ranks of the low rank blocks grow and the data-sparsity gets lost. We will explain this behavior by applying a theorem on the structure preservation of diagonal plus semiseparable matrices under LR Cholesky transformations. Therefore we have to give a new more constructive proof for the theorem. We will show that the structure of Hℓ-matrices is almost preserved and so the LR Cholesky algorithm is of almost quadratic complexity for Hℓ-matrices.

AB - We investigate the application of the LR Cholesky algorithm to symmetric hierarchical matrices, symmetric simple structured hierarchical matrices and symmetric hierarchically semiseparable (HSS) matrices. The data-sparsity of these matrices make the otherwise expensive LR Cholesky algorithm applicable, as long as the data-sparsity is preserved. We will see in an example that the ranks of the low rank blocks grow and the data-sparsity gets lost. We will explain this behavior by applying a theorem on the structure preservation of diagonal plus semiseparable matrices under LR Cholesky transformations. Therefore we have to give a new more constructive proof for the theorem. We will show that the structure of Hℓ-matrices is almost preserved and so the LR Cholesky algorithm is of almost quadratic complexity for Hℓ-matrices.

KW - Eigenvalues

KW - Hℓ-Matrices

KW - LR Cholesky algorithm

KW - Semiseparable matrices

KW - Symmetric hierarchical matrices

UR - http://www.scopus.com/inward/record.url?scp=84879881157&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879881157&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2013.03.001

DO - 10.1016/j.laa.2013.03.001

M3 - Article

AN - SCOPUS:84879881157

VL - 439

SP - 1150

EP - 1166

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 4

ER -