Steffen Börm: Veröffentlichungen

2010

[Börm2010b]
Steffen Börm: Efficient Numerical Methods for Non-local Operators: H²-Matrix Compression, Algorithms and Analysis.
EMS Tracts in Mathematics Vol 14 (2010)
H²-Matrizen bieten die Möglichkeit, vollbesetzte Matrizen, die beispielsweise bei der Diskretisierung nicht-lokaler Operatoren oder als Lösungsoperatoren elliptischer Differentialgleichungen auftreten, effizient zu speichern und zu verarbeiten. Dieses Buch bietet eine umfassende Darstellung des Stands der Forschung zu diesem Thema und behandelt

• Algorithmen für die Konstruktion von H²-Matrizen,
• Approximationsaussagen für Integralgleichungen und elliptische partielle Differentialgleichungen sowie
• effiziente Verfahren für die Matrix-Arithmetik, etwa für die Konstruktion von Vorkonditionierern für lineare Gleichungssysteme.

[Börm2010]
Steffen Börm: Approximation of solution operators of elliptic partial differential equations by H- and H²-matrices.
Numerische Mathematik, 115:165-193 (2010)
Bei der Behandlung elliptischer partieller Differentialgleichungen besteht ein großer Vorteil hierarchischer Matrizen im Vergleich zu Mehrgitterverfahren darin, dass sie springende und anisotrope Koeffizienten ohne besondere Anpassungen der Algorithmen handhaben können. In diesem Artikel entwickele ich eine verbesserte Variante des ersten Approximationsresultats von Bebendorf und Hackbusch und zeige, dass es sich auf H²-Matrizen übertragen lässt und dadurch der Speicherbedarf deutlich gesenkt werden kann.
MPI Preprint 85/2007 Num. Math.

2009

[Börm2009]
Steffen Börm: Construction of data-sparse H²-matrices by hierarchical compression.
SIAM J. Sci. Comput., 31:1820--1839 (2009)
Aus algorithmischer Sicht besitzen H-Matrizen eine relativ einfache Struktur: Die Matrix wird in eine Hierarchie von Untermatrizen zerlegt, und jede Untermatrix wird durch niedrigen Rang approximiert. Da alle Untermatrizen voneinander unabhängig sind, können viele Berechnung mit Hilfe sehr einfacher rekursiver Algorithm durchgeführt werden. Bei H²-Matrizen wird eine zusätzliche geschachtelte Hierarchie von Ansatzrämen eingeführt, die die Effizienz der Darstellung deutlich verbesserm können, aber es bisher erforderlich machten, Algorithmen so zu entwerfen, dass die Hierarchie auch bei allen Zwischenergebnissen erhalten bleibt. In diesem Artikel führe ich eine einfache Technik ein, mit der sich eine beliebige H-Matrix in eine H²-Matrix konvertieren lässt, indem alle Teilblöcke zunächst unabhängig aufgestellt und die Hierarchie der Ansatzräme dann rekonstruiert wird. Die resultierenden Verfahren sind ähnlich einfach und flexibel wie H-Matrix-Algorithmen, benötigen aber bei großen Problemen wesentlich weniger Speicher, da alle Zwischenergebnisse als H²-Matrizen dargestellt werden.
MPI Preprint 92/2007 SISC

2008

[Banjai/Börm/Sauter2008]
Lehel Banjai, Steffen Börm und Stefan A. Sauter: FEM for elliptic eigenvalue problems: How coarse can the coarsest mesh be chosen? An experimental study.
Computing and Visualization in Science, 11:363-372 (2008)
Die üblichen Fehlerabschätzungen für die Behandlung von Eigenwertproblemen mit Hilfe von Galerkin-Diskretisierungen, etwa mittels der Finite-Elemente-Methode, sind asymptotischer Natur: Sofern die Gitterschrittweite klein genug ist, konvergiert die Finite-Elemente-Approximation des Eigenvektors mit der optimalen Rate. In diesem Artikel untersuchen wir, wie klein "klein genug" eigentlich ist, indem wir das Eigenwert-Mehrgitterverfahren auf Modellprobleme anwenden und systematisch die Approximationsgüte verschiedener Eigenvektoren analysieren.
CVS

[Bendoraityte/Börm2008]
Joana Bendoraityte und Steffen Börm: Distributed H²-matrices for non-local operators
Computing and Visualization in Science, 11:237-249 (2008)
H²-Matrizen sind eine Technik zur Darstellung vollbesetzter Matrizen, deren Speicherbedarf, anders als bei der üblichen Darstellung durch zweidimensionale Arrays, lediglich linear mit der Anzahl der Unbekannten wächst. Dadurch wird dieser Zugang sehr attraktiv für die Behandlung großer Probleme. Da sehr große Probleme in der Regel mit Hilfe verteilter Rechner behandelt werden, stellt sich die Frage, wie H²-Matrizen auf derartigen Architekturen umgesetzt werden können. Dieser Artikel schlägt eine Vorgehensweise vor, die beweisbar eine fast perfekte parallele Effizienz erzielt.
CVS

2007

[Börm/Garcke2007]
Steffen Börm und Jochen Garcke: Approximating Gaussian processes with H²-matrices
Machine Learning ECML 2007, J. Fürnkranz, S. Dzeroski, H. Blockeel, J. Ramon, P. Flach, Z.-H. Zhou, D. Roth (Hrsg.), 42-53, Springer 2007

[Börm2005b]
Steffen Börm: Adaptive variable-rank approximation of general dense matrices
SIAM Journal of Scientific Computing, 30:148-168, 2007
Verfahren variabler Ordnung nach Sauter haben das Ziel, datenschwache Approximationen diskretisierter Integraloperatoren zu konstruieren, die die optimale Komplexität O(n) in der Anzahl n der Unbekannten erreichen und außerdem dafür sorgen, dass der Approximationsfehler nicht größer als der Diskretisierungsfehler ist. Die Analyse derartiger Verfahren ist in der Regel relativ kompliziert und hängt stark von dem zugrundeliegenden Problem ab. In diesem Artikel stelle ich einen Algorithmus vor, der Approximationen variabler Ordnung für allgemeine Matrizen automatisch bestimmt: Falls eine gegebene Matrix sich durch eine H²-Matrix approximieren lässt, wird dieser Algorithmus diese Approximation ohne weitere Hilfestellung konstruieren.
MPI Preprint 114/2005 SISC

[Börm2005]
Steffen Börm: Data-sparse approximation of non-local operators by H²-matrices
Linear Algebra and its Applications, 422:380-403, 2007
H²-Matrizen erzielen ihre hohe Effizienz, indem sie eine geeignet konstruierte geschachtelte Basis zur Approximation der zulässigen Blöcke einsetzen. Bei der Anwendung auf klassische Integraloperatoren ergibt sich die Existenz dieser Basis aus der Taylor-Entwicklung oder Interpolation der zugrundeliegenden Kernfunktion, in allgemeineren Situationen dagegen ist die Frage nach der Existenz einer effizienten Basis weniger einfach zu beantworten. In diesem Artikel entwickele ich ein theoretisches Grundgerüst, mit dessen Hilfe sich auch in relativ allgemeinen Situationen die Frage nach der Existenz geschachtelter Basen analysieren lässt. Am Beispiel einiger Integral- und Differentialgleichungen demonstriere ich, wie die Theorie sich einsetzen lässt, um neue Approximationsresultate zu beweisen.
MPI Preprint 44/2005 LAA

2006

[Börm2004b]
Steffen Börm: H²-matrix arithmetics in linear complexity
Computing 77:1-28, 2006
Einer der wesentlichen Vorteile hierarchischer Matrizen besteht darin, dass sich mit ihrer Hilfe arithmetische Operationen wie die Addition, Multiplikation oder Inversion solcher Matrizen in fast lineare Komplexität approximativ durchführen lassen. In diesem Kontext bedeutet "fast", dass in Theorie und Praxis zusätzliche logarithmische Faktoren auftreten. In diesem Artikel stelle ich Algorithmen vor, mit denen sich diese Faktoren bei H²-Matrizen vermeiden lassen: Die beste Approximation der Summe oder des Produkts zweier H²-Matrizen in einer gegebenen Matrixstruktur kann so in linearer Komplexität berechnet werden. Numerische Experimente zeigen, dass die resultierenden Verfahren wesentlich schneller als die bekannten H-Matrix-Techniken sein können.
MPI Preprint 47/2004 Computing.

2005

[Börm/Sauter2005]
Steffen Börm und Stefan A. Sauter: BEM with linear complexity for the classical boundary integral operators
Mathematics of Computation, 74:1139-1177, 2005
Math. Comp.

[Börm/Grasedyck2004]
Steffen Börm, Lars Grasedyck: Hybrid cross approximation of integral operators.
Numerische Mathematik, 101:221-249, 2005
Ein beliebter Ansatz zur Konstruktion von Niedrigrang-Approximationen diskretisierter Integraloperatoren beruht auf der Anwendung von Kreuzapproximationstechniken nach Tyrtyshnikov und Bebendorf/Rjasanow. Dieser Ansatz hat den Vorteil, dass eine H-Matrix-Approximation sehr einfach aus einigen wenigen adaptiv gewählten Matrixeinträgen konstruiert werden kann. Bedauerlicherweise gibt es Situationen, in denen der populäre ACA-Algorithmus fehlschlägt: Es gibt Beispiele, bei denen das Verfahren meldet, dass eine gute Approximation konstruiert wurde, obwohl das nicht der Fall ist. Die Ursache liegt darin, dass während des Übergangs vom kontinuierlichen zum diskreten Problem zuviel Information verloren geht. Wir stellen einen modifizierten Zugang vor: Es wird eine Kreuzapproximation der zugrundeliegenden Kernfunktion berechnet, und erst diese Approximation wird diskretisiert, um zu einer H-Matrix zu gelangen. Wir führen den Beweis, dass dieser Ansatz konvergiert, und demonstrieren anhand numerischer Beispiele, dass die hybride Technik schneller und zuverlässiger als ihr Vorläfer ist.
MPI Preprint 68/2004 Num. Math.

[Börm2004a]
Steffen Börm: Approximation of integral operators by H²-matrices with adaptive bases
Computing, 74:249-271, 2005
Mit Hilfe von Kernapproximationen (etwa per Taylor- oder Multipol-Entwicklung oder Interpolation) konstruierte H²-Matrizen enthalten üblicherweise redundante Informationen, weil die zugrundelegende kontinuierliche Technik besondere Eigenschaften der Geometrie oder der Diskretisierung nicht berücksichtigen kann. In diesem Artikel stelle ich zwei Ansätze vor, mit denen sich die Effizienz verbessern lässt: Die Orthogonalisierung identifiziert im Zuge der Diskretisierung überflüssig gewordene Entwicklungsfunktionen, die Rekompression geht einen Schritt weiter und berücksichtigt auch die Kernfunktion.
MPI Preprint 18/2004

[Börm/Hackbusch2003c]
Steffen Börm und Wolfgang Hackbusch: Hierarchical quadrature of singular integrals
Computing, 74:75-100, 2005
MPI Preprint 50/2003

[Börm/Krzebek/Sauter2005]
Steffen Börm, Nico Krzebek und Stefan A. Sauter: May the singular integrals in BEM be replaced by zero?
Computer Methods in Applied Mechanics and Engineering, 194:383-393, 2005
MPI Preprint 86/2003

[Börm/Löhndorf/Melenk2002]
Steffen Börm, Maike Löhndorf und J. Markus Melenk: Approximation of integral operators by variable-order interpolation
Numerische Mathematik 99:605-643, 2005.
MPI Preprint 82/2002 Num. Math.

2004

[Börm2004c]
Steffen Börm: Fast evaluation of eddy current integral operators
Numerical Mathematics and Advanced Applications - ENUMATH 2003, M. Feistauer, V. Dolejsi, P. Knobloch, K. Najzar (Hrsg.), 151-158, Springer 2004.

[Börm2003]
Steffen Börm: H²-matrices - Multilevel methods for the approximation of integral operators
Computing and Visualization in Science, 7:173-181, 2004.
MPI Preprint 7/2003

[Börm/Hackbusch2003a]
Steffen Börm und Wolfgang Hackbusch: Approximation of boundary element operators by adaptive H²-matrices
Foundations of Computational Mathematics, Minneapolis 2002, F. Cucker, R. DeVore, P. Olver und P. Süli (Hrsg.), London Mathematical Society Lecture Note Series 312:58-75, 2004.
MPI Preprint 5/2003

[Börm/Grasedyck2002]
Steffen Börm und Lars Grasedyck: Low-rank approximation of integral operators by interpolation
Computing, 72:325-332, 2004.
MPI Preprint 72/2002

2003

[Börm/Grasedyck/Hackbusch2003]
Steffen Börm, Lars Grasedyck, Wolfgang Hackbusch: Hierarchical matrices
Dieses Skript ist die Grundlage der Winterschulen über hierarchische Matrizen, die seit 2003 jährlich durch das Max-Planck-Institut veranstaltet werden. Beschrieben werden verschiedene Techniken zur Konstruktion von Niedrigrangapproximationen, Clusterungstechniken, approximative Arithmetik, Komplexitätsabschätzungen, H²-Matrizen und die Anwendung dieser Techniken auf Integralgleichungen, elliptische partielle Differentialgleichungen sowie Anwendungen aus der Steuerungstheorie. Außerdem enthält das Skript eine Beschreibung der grundlegenden und auch einiger der aufwendigeren Funktionen und Strukturen der HLib.
MPI Lecture Note 21/2003

[Börm/Hackbusch2003b]
Steffen Börm, Wolfgang Hackbusch: A short overview of H²-matrices
Proceedings in Applied Mathematics and Mechanics, 2:33-36, 2003.

[Börm/Ostrowski2003]
Steffen Börm, Jörg Ostrowski: Fast evaluation of boundary integral operators arising from an eddy current problem
Journal of Computational Physics, 193:67-85, 2003.
MPI Preprint 33/2003 J. Comp. Phys.

[Börm/Grasedyck/Hackbusch2003]
Steffen Börm, Lars Grasedyck und Wolfgang Hackbusch: Introduction to hierarchical matrices with applications
Engineering Analysis with Boundary Elements, 27:405-422, 2003.
MPI Preprint 18/2002

[Börm/Hackbusch2003]
Steffen Börm und Wolfgang Hackbusch: A short overview of H²-matrices
Proceedings in Applied Mathematics and Mechanics, 2:33-36, 2003.

2002

[Börm/Hiptmair2002]
Steffen Börm, Ralf Hiptmair: Multigrid computation of axisymmetric electromagnetic fields
Advances in Computational Mathematics, 16:331-356, 2002.
Adv. in Comput. Math.

[Börm/Grasedyck/Hackbusch2002]
Steffen Börm, Lars Grasedyck, Wolfgang Hackbusch: An introduction to hierarchical matrices
Mathematica Bohemica, 127(2):229-241, 2002.
MPI Preprint 105/2001

[Börm/Hackbusch2002b]
Steffen Börm, Wolfgang Hackbusch: H²-matrix approximation of integral operators by interpolation
Applied Numerical Mathematics, 43:129-143, 2002.
MPI Preprint 104/2001

[Börm/Hackbusch2002a]
Steffen Börm, Wolfgang Hackbusch: Data-sparse approximation by adaptive H²-matrices
Computing, 69:1-35, 2002.
Während die Konstruktion der bestmöglichen Approximation einer allgemeinen Matrix durch eine HMatrix eine einfache Anwendung der Singulärwertzerlegung ist, gestaltet sich die Situation bei den effizienteren H²-Matrizen deutlich komplizierter, da die einzelnen Blöcke nicht unabhängig voneinander behandelt werden können und außerdem die geschachtelte Struktur der verwendeten Basen sichergestellt werden muss. In diesem Artikel stellen wir einen Algorithmus vor, der sehr effizient eine fast optimal H²-Matrix-Approximation konstruiert.
MPI Preprint 86/2001

2001

[Börm2001]
Steffen Börm: Tensor product multigrid for Maxwell's equation with aligned anisotropy
Computing, 66:321-342, 2001.
Der in [Börm/Hiptmair2001] vorgestellte Algorithmus lässt sich mit Hilfe einer etwas verallgemeinerten Technik auch auf vektorwertige Probleme anwenden. In diesem Artikel wird bewiesen, dass sich beispielsweise die der Theorie elektromagnetischer Felder zugrundeliegenden Maxwell-Gleichungen auf diesem Wege robust in linearer Komplexität behandeln lassen.
Computing

[Börm/Hiptmair2001]
Steffen Börm, Ralf Hiptmair: Analysis of tensor product multigrid
Numerical Algorithms, 26:219-234, 2001.
Dieser Artikel behandelt ein Mehrgitterverfahren, das für in einer Koordinatenrichtung singulär gestörte elliptische Differentialgleichungen robust konvergiert. Eine wichtige Anwendung sind Gleichungen, die durch Koordinatentransformation, etwa in Zylinderkoordinaten, entstehen, und die sich mit diesem Verfahren in linearer (also optimaler) Komplexität lösen lassen.
Num. Alg.

2000

[Börm/Hackbusch2000]
Steffen Börm, Wolfgang Hackbusch: Computation of Electromagnetic Fields for a Humidity Sensor
Mathematics - Key Technology for the Future. Joint Projects between Universities and Industry. W. Jäger und H.-J. Krebs (Hrsg.), Springer, 2000