HOMEContact | Local | Impressum | German
Minerva Logo of the MPG
Photo of the Institute
Banner Max-Planck-Institut
Research Group Computational Methods in Systems and Control Theory

Diese Seite wird nicht mehr aktualisiert. Bitte besuchen Sie unsere neue Webpräsenz.

This page is not updated any longer. Please visit our new website.

Algorithms for Rank and Tensor Structured Matrices

Researcher:

  • Thomas Mach
    Max Planck Institute for Dynamics of Complex Technical Systems Magdeburg,
    Computational Methods in Systems and Control Theory,
    Tel: +49 (0)391-6110-806
    E-mail: thomas.mach@googlemail.com

Project Description

Roadmap Large dense matrices can often not be handled with standard algorithms due to the limitation of storage. Special algorithms make use of the structure of the matrix. We investigate matrices with hierarchical rank structure (see [1]) and tensor-train structure (see [2]).

Often it is necessary to compute the eigenvalues of a matrix. The eigenvalues are important to determine the properties of the matrix and the problem behind. Sometimes it is not enough to know some eigenvalues, e.g. in the Anderson-model in particle physics.

The storage of hierarchical matrices (ℋ-matrices) needs a lower amount in compare to full matrices, so they are data-sparse matrices. Many matrix operation for ℋ-matrices only needs linear-polylogarithmic time.

One goal of this project is to find (if possible) all eigenvalues of an ℋ-matrix. These algorithms will be tested and evaluated at selected examples.

We also investigate the computation of some eigenvalues of matrices given in tensor-train matrix structure.

Duration and Funding

  • May 2008 - September 2010: Chemnitz University of Technology funded by a grant from the Free State of Saxony (Sächsisches Landesstipendium)
  • October 2010 - June 2012: MPI Magdeburg

Poster

Related Publications

@Article{BenM12,
author = {P. Benner and T. Mach},
title = {The Preconditioned Inverse Iteration for Hierarchical Matrices},
year = 2013,
journal = {Numer. Lin. Alg. Appl.},
doi = {10.1002/nla.1830},
pages = {150--166},
volume=20,
number=1 }
The Preconditioned Inverse Iteration for Hierarchical Matrices;
Benner, Peter; Mach, Thomas;
Numer. Lin. Alg. Appl.  :  Vol. 20, No. 1, 150-166;
2013.
DOI: 10.1002/nla.1830
also available as preprint MPIMD/11-01, 17 pages.
@Article{BenM12b,
author = {Peter Benner and Thomas Mach},
title = {Computing All or Some Eigenvalues of Symmetric $\mathcal{H}_{\ell}$-Matrices},
publisher = {SIAM},
year = {2012},
journal = {SIAM Journal on Scientific Computing},
volume = {34},
number = {1},
pages = {A485-A496},
keywords = {symmetric hierarchical matrices; eigenvalues; $\mathcal{H}_{\ell}$-matrices; slicing the spectrum},
url = {http://link.aip.org/link/?SCE/34/A485/1},
doi = {10.1137/100815323} }
Computing all or some Eigenvalues of symmetric ℋ-Matrices;
Benner, Peter; Mach, Thomas;
SIAM Journal of Scientific Computing  :  Vol. 34, No. 1, A485-A496;
2012.
DOI: 10.1137/100815323
also available as preprint MPIMD/10-01.
@TECHREPORT{MPIMD12-05,
author = {Peter Benner and Thomas Mach},
title = {The LR Cholesky Algorithm for Symmetric Hierarchical Matrices},
number = {MPIMD/12-05},
month = {February},
year = 2012,
type = {MPI Magdeburg Preprint},
note = {Available from \url{http://www.mpi-magdeburg.mpg.de/preprints/}},
}
The LR Cholesky Algorithm for Symmetric Hierarchical Matrices;
Benner, Peter; Mach, Thomas ;
2012.
available as preprint MPIMD/12-05, 16 pages.
@TECHREPORT{MPIMD11-09,
author = {Thomas Mach},
title = {Computing Inner Eigenvalues of Matrices in Tensor Train Matrix Format},
institution = {Max Planck Institute Magdeburg Preprints},
year = 2011,
number = {MPIMD/11-09},
month = {December} }
Computing Inner Eigenvalues of Matrices in Tensor Train Matrix Format;
Mach, Thomas;
in A. Cangiani, R.L. Davidchack, E.H. Georgoulis, A. Gorban, J. Levesley, M.V. Tretyakov: Numerical Mathematics and Advanced Applications 2011 - Proceedings of ENUMATH 2011, the 9th European Conference on Numerical Mathematics, Leicester  :  
Springer; 2012.
accepted, available as preprint MPIMD/11-09, 11 pages.
@InProceedings{MacS12,
author = {T. Mach and J. Saak},
title = {How Competitive is the ADI for Tensor Structured Equations?},
journal = {PAMM},
volume = {12},
number = {1},
publisher = {WILEY-VCH Verlag},
issn = {1617-7061},
year = {2011},
note = {DOI: 10.1002/pamm.201210306},
}
How Competitive is the ADI for Tensor Structured Equations?;
Mach, Thomas; Saak, Jens;
Proceedings in Applied Mathematics and Mechanics  :  
Wiley InterScience; 2012.
Pages: 635–636, DOI: 10.1002/pamm.201210306.
@article {BenM11d,
author = {P. Benner and T. Mach},
title = {Locally Optimal Block Preconditioned Conjugate Gradient Method for Hierarchical Matrices},
journal = {PAMM},
volume = {11},
number = {1},
publisher = {WILEY-VCH Verlag},
issn = {1617-7061},
url = {http://dx.doi.org/10.1002/pamm.201110360},
doi = {10.1002/pamm.201110360},
pages = {741--742},
year = {2011},
}
Locally Optimal Block Preconditioned Conjugate Gradient Method for Hierarchical Matrices;
Benner, Peter; Mach, Thomas;
Proceedings in Applied Mathematics and Mechanics  :  Volume 11, Issue 1, pages 741–742, December 2011;
Wiley InterScience; 2011.
DOI: 10.1002/pamm.201110360.
@TECHREPORT{MPIMD11-12,
author = {Thomas Mach, Jens Saak},
title = {Towards an ADI iteration for Tensor Structured Equations},
institution = {Max Planck Institute Magdeburg Preprints},
year = 2011,
number = {MPIMD/11-12},
month = {December} }
Towards an ADI iteration for Tensor Structured Equations;
Mach, Thomas; Saak, Jens;
Max Planck Institute Magdeburg Preprints, MPIMD/11-12;
2011.
16 pages.
@ARTICLE{BenM10,
author = {Peter Benner and Thomas Mach},
title = {{O}n the {QR} {D}ecomposition of $\mathcal{H}$-{M}atrices},
year = {2010},
journal = {Computing},
volume = {88},
number = {3--4},
pages = {111--129} }
On the QR Decomposition of ℋ-Matrices;
Benner, Peter; Mach, Thomas;
Computing  :  Vol. 88, No. 3-4, pp. 111-129;
Springer; 2010.
DOI: 10.1007/s00607-010-0087-y
see also CSC preprint 09-04.
154Computing the Eigenvalues of Hierarchical Matrices by LR-Cholesky Transformations;
Benner, Peter; Mach, Thomas;
Mathematisches Forschungsinstitut Oberwolfach, Report No. 37/2009, pp. 325-328;
Mathematisches Forschungsinstitut Oberwolfach; 2009.
DOI: 10.4171/OWR/2009/37.

References

 Top
Thomas Mach, thomas.mach@googlemail.com