Loading…
Thumbnail Image

Recycling Krylov subspace methods for sequences of linear systems

Gaul, André

Inst. Mathematik

In vielen Anwendungen ist das Lösen einer Folge linearer Gleichungssysteme mit sich verändernden Matrizen und rechten Seiten erforderlich. Diese Dissertation widmet sich der Analyse und den Anwendungen von Recycling in Krylov-Unterraumverfahren um solche Folgen effizient zu lösen. Im Rahmen der Arbeit werden sowohl die Wohldefiniertheit von CG, MINRES und GMRES mit deflation als auch deren Verhältnis zu Methoden mit augmentation untersucht. Zudem werden die Auswirkungen von Störungen auf Projektionen, Spektren von projizierten Matrizen sowie Krylov-Unterraumverfahren im Allgemeinen studiert. Für Verfahren mit deflation führen die Untersuchungen auf Konvergenzschranken, die bei der automatischen Auswahl von Recycling-Daten als Entscheidungshilfe benutzt werden können. Eine neuartige Konvergenzschranke basiert auf approximativen Krylov-Unterräumen und verschafft auch im Falle nicht-normaler Matrizen wertvolle Informationen über das Konvergenzverhalten von GMRES. Numerische Experimente mit nichtlinearen Schrödinger-Gleichungen zeigen, dass die in der Arbeit hergeleiteten automatischen Recyclingstrategien die Gesamtrechenzeit um bis zu 40% senken.
In several applications, one needs to solve a sequence of linear systems with changing matrices and right hand sides. This thesis concentrates on the analysis and application of recycling Krylov subspace methods for solving such sequences efficiently. The well-definedness of deflated CG, MINRES and GMRES methods and their relationship to augmentation is analyzed. Furthermore, the effects of perturbations on projections, spectra of deflated operators and Krylov subspace methods are studied. The analysis leads to convergence bounds for deflated methods which provide guidance for the automatic selection of recycling data. A novel approach is based on approximate Krylov subspaces and also gives valuable insight in the case of non-normal operators. Numerical experiments with nonlinear Schrödinger equations show that the overall time consumption is reduced by up to 40% by the derived automatic recycling strategies.
  • Der LaTeX-Code sowie der Source-Code aller Experimente ist unter https://github.com/andrenarchy/phdthesis verfügbar.