Bergische Universität Wuppertal Fachbereich Mathematik und Naturwissenschaften Angewandte Mathematik - Numerische Analysis (AMNA)

People Research Publications Teaching

---

In diesem Numerik-Seminar werden schnelle 'state-of-the-art', meist analysis-basierte, numerische Methoden behandelt. Diese Algorithmen dienen meist der Lösung von Differential- oder Integralgleichungen oder der effektiven Berechnung von diskreten Summationen, Faltungen, Transformationen usw. Ein Schwerpunkt werden die schnellen Multipol-Methoden und ihre Abkömmlinge bilden. Jack Dongarra und Francis Sullivan veröffentlichten in der Zeitschrift Computing in Science & Engineering (Januar 2000 Vol. 2, Issue 1, Seiten 2-97) Die Top Ten Algorithmen des 20. Jahrhunderts; dies ist die Motivation für dieses Seminar.

1. Schnelle Fourier Transformation (für nicht-uniforme Daten)
2. Allgemeine Schnelle Summationstechniken und Transformationen
3. Schnelle Multipol-Methoden
4. Schnelle Gauß-Transformation
5. Schnelle Algorithmen für elliptische PDGl
6. Schnelle Algorithmen für Randwertprobleme
7. Schnelle Algorithmen für die Wärmeleitungsgleichung
8. Schnelle Algorithmen für die Wellengleichung
9. Verallgemeinerte Gauß-Quadratur und Summe-von-Potenzen Approximation
10. Schnelle Algorithmen für Absorbierende Randbedingungen

Die Einteilung der Gruppen erfolgt auf Grund der Kenntnisse, Interessen und Möglichkeiten der TeilnehmerInnen. Die Zusammensetzung der Gruppen erfolgt unter dem Gesichtspunkt der Komplementarität. Analytisch besonders Interessierte sollen mit numerisch Versierten und Computercracks zusammenarbeiten. Im Idealfall wird jeder Vortrag von einem anderen Gruppenmitglied gehalten. Dabei kommt jedem/jeder TeilnehmerIn in unterschiedlichen Phasen des Seminars eine Führungsrolle zu.

Scheinkriterium:

  Präsentation

• Erläuterung des Anwendungsproblems
• Mathematische Modellierung (evtl. mehrstufig)
• Lösung / Analyse / Numerik
• Diskussion der Resultate und ihrer Relevanz für die Anwendung
• Für die Präsentation wird Prosper bzw. HA-Prosper oder PPower4 empfohlen
  ( Verschiedene Präsentationsprogramme)
• Evtl. numerische Simulationen (möglichst in Matlab, Scilab oder Octave)
  Schriftliche Ausarbeitung (ca. 10 Seiten, inkl. Beispiele)
  Regelmässige Teilnahme am Seminar

Vorkenntnisse:
Basiswissen mathematischer Grundvorlesungen wird vorausgesetzt.
Wünschenswert ist eine erfolgreiche Teilnahme an Lehrveranstaltungen der praktischen und numerischen Mathematik sowie Grundkenntnisse der Theorie und Numerik partieller Differentialgleichungen.

Literatur: (wird im Seminar ausgegeben)

1. • A. Dutt und V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput. 14 (1993), 1368-1393.
   • A. Dutt und V. Rokhlin, Fast Fourier transforms for nonequispaced data. II, Appl. Comput. Harmon. Anal. 2 (1995), 85-100.
   • L. Greengard und J.-Y. Lee, Accelerating the nonuniform fast Fourier transform, SIAM Rev. 46 (2004), 443-454
   • D. Potts, The Nonequispaced FFT: An Indispensable Algorithm for Applied Science, Computing Reviews, 2008.
2. • P. Deuflhard, A Summation Technique for Minimal Solutions of Linear Homogeneous Difference Equations, Computing 18 (1977) , 1-13.
   • M. O'Neal und V. Rokhlin, A new class of analysis-based fast transforms, Technical Report 1384, Yale University, Department of Computer Science, 2007.
   • M. Tygert, Recurrence relations and fast algorithms, Technical Report 1343, Yale University, Department of Computer Science, 2005.
   • M. Tygert, Fast algorithms for spherical harmonic expansions II, Technical Report 1381, Yale University, Department of Computer Science, 2007.
3. • V. Rokhlin, Rapid solution of integral equations of scattering theory in two dimensions, J. Comput. Phys. 86 (1990), 414-439.
   • L. Greengard und V. Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta numerica 6 (1997), 229-269.
   • Th. Hrycak und V. Rokhlin, An improved fast multipole algorithm for potential fields, SIAM J. Sci. Comput. 19 (1998), 1804-1826
   • X. Sun und N.P. Pitsianis, A matrix version of the fast multipole method, SIAM Rev. 43 (2001), 289-300.
   • L. Ying, G. Biros und D. Zorin, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, J. Comput. Phys. 196 (2004), 591-626.
4. • L. Greengard und J. Strain, The fast Gauss transform, SIAM J. Sci. Statist. Comput. 12 (1991), 79-94.
   • J. Strain, The fast Gauss transform with variable scales, SIAM J. Sci. Statist. Comput. 12 (1991), 1131-1139.
   • F. Andersson und G. Beylkin, The fast Gauss transform with complex parameters, J. Comput. Phys. 203 (2005), 274-286.
5. • F. Ethridge, Frank und L. Greengard, A new fast-multipole accelerated Poisson solver in two dimensions, SIAM J. Sci. Comput. 23 (2001), 741-760.
   • N. Nishimura, Fast multipole accelerated boundary integral equation methods, Appl. Mech. Rev. 55 (2002), 299-324.
   • L. Ying, Lexing, G. Biros und D. Zorin, A high-order 3D boundary integral equation solver for elliptic PDEs in smooth domains, J. Comput. Phys. 219 (2006), 247-275.
6. • J.-Y. Lee und L. Greengard, A fast adaptive numerical method for stiff two-point boundary value problems, SIAM J. Sci. Comput. 18 (1997), 403-429.
7. • L. Greengard und J. Strain, A fast algorithm for the evaluation of heat potentials, Comm. Pure Appl. Math. 43 (1990), 949-963.
   • J. Strain, Fast adaptive methods for the free-space heat equation, SIAM J. Sci. Comput. 15 (1994), 185-206.
   • S.K. Veerapaneni und G. Biros, A fast high-order integral equation solver for the heat equation with moving boundaries in 1d, SIAM J. Sci. Comput. 29 (2007), 2581-2606
8. • A. Ergin, B. Shanker und E. Michielssen, Fast evaluation of three-dimensional transient wave fields using diagonal translation operators, J. Comput. Phys. 146 (1998), 157-180.
   • E. Michielssen, A. Ergin, B. Shanker und D. Weile, The multilevel plane wave time domain algorithm and its applications to the rapid solution of electromagnetic scattering problems: a review in: Mathematical and numerical aspects of wave propagation, SIAM, 2000, Seiten 24-33.
9. • G. Beylkin und L. Monzón, On generalized Gaussian quadratures for exponentials and their applications, Appl. Comput. Harmon. Anal. 12 (2002), 332-373.
   • G. Beylkin und L. Monzón, On approximation of functions by exponential sums, Appl. Comput. Harmon. Anal. 19 (2005), 17-48.
   • J. Ma, V. Rokhlin und S. Wandzura, Generalized Gaussian quadrature rules for systems of arbitrary functions, SIAM J. Numer. Anal. 33 (1996), 971-996.
   • N. Yarvin und V. Rokhlin, V. Generalized Gaussian quadratures and singular value decompositions of integral operators, SIAM J. Sci. Comput. 20 (1998), 699-718.
10. • B. Alpert, L. Greengard und Th. Hagstrom, Rapid evaluation of nonreflecting boundary kernels for time-domain wave propagation, SIAM J. Numer. Anal. 37 (2000), 1138-1164.
    • B. Alpert, L. Greengard und Th. Hagstrom, Nonreflecting boundary conditions for the time-dependent wave equation, J. Comput. Phys. 180 (2002), 270-296.
    • X. Antoine, A. Arnold, C. Besse, M. Ehrhardt and A. Schädle, A Review of Transparent and Artificial Boundary Conditions Techniques for Linear and Nonlinear Schrödinger Equations, Commun. Comput. Phys. Vol. 4, Number 4, (2008), 729-796. (open-access article)
      supplementary material (Matlab codes):
      • MATLAB GUI
      • Talks from the ICIAM07 Minisymposium

Links:

• The SIAM 100-Dollar, 100-Digit Challenge (Nick Trefethen, Oxford University)
• The SIAM 100-Digit Challenge Book (Bornemann, Laurie, Wagon & Waldvogel)
  • German Version: Vom Lösen numerischer Probleme (Bornemann, Laurie, Wagon & Waldvogel)
• 100-Digit Challenge Problems (Stan Wagon, Macalester College, St. Paul, Minnesota)

Didaktische Vortragstipps:
Wie halte ich einen Seminarvortrag (M.Lehn, Mainz)
Artikel 1, Artikel 2, Artikel 3

Ähnliche Vorlesung im Sommersemester 2011