Possible Topics in Applied Mathematics

LEAST-SQUARES FINITE ELEMENT METHODS FOR PDEs

Said more generally, the least-squares objective is to redesign the original problem (PDE) so that an accurate numerical solution (including the discretization and algebraic solvers) is relatively easy to obtain. Because of this focus on the design of the problem in the function space setting, theory for this approach is critical and relevant to practice. The course will therefore have a significant theoretical component that lays the foundation for the practical aspects.

The course lectures will be based on a collection of notes, research papers and monographs, and computer applications. In lieu of tests and homework, we will have several projects, starting with common assignments involving basic and more advanced schemes, then culminating in individual efforts submitted and presented at the end of the term.

Outline

1. Sobolev Spaces: Basic spaces, essential theorems, and fundamental principles.
2. Finite Elements: Abstract concepts, practical methodology, approximation properties.
3. Multigrid Overview: Simplified optimal elliptic solvers, basic concepts.
4. FOSLS: Objectives, methodology for model problems, basic theory, practical results.
5. FOSLS Algorithms: Properties for model problems, implementation concepts.
6. Advanced Methods: Nonlinear schemes, adaptive refinement, discontinuities, inverse norm schemes, parameter dependence
7. Application Menu: General elliptic systems, Stokes, Navier-Stokes, high Reynolds flow, elasticity, electromagnetics, inverse problems.

The development of modern multigrid methods for solving partial differential equations began in the 70s, but has become a widely used tool only fairly recently. It began as a general fast elliptic solver (some claim it's the fastest for many problems), but has now expanded into many areas of application, some of which include such diverse areas as aerodynamics, astrophysics, chemistry, electromagnetics, hydrology, medical imaging, meteorology/oceanography, quantum mechanics, and statistical physics. The purpose of this course is to develop a fundamental understanding of the principles and techniques of the multigrid methodology, beginning with a basic foundation on iterative methods in general, smoothers in particular, and elliptic multigrid solvers. This first part will be based on the first five chapters of the second edition of the monograph A Multigrid Tutorial by W. Briggs, V. Henson, and S. McCormick.

The rest of the course will be based in part on the remaining five chapters of the monograph. It will develop more sophisticated multigrid methodologies and algorithms, and these will be applied to a more diverse collection of problems. Some of the coursework may be tailored to student interests.

These lectures will be based the monograph supplemented by a collection of notes and other research materials. In lieu of tests and homework, we will have several projects, starting with common assignments involving basic and more advanced multigrid schemes, then culminating in individual efforts submitted and presented by the students at the end of the term.

Outline

1. Basic Tutorial: model problems, basic iterative methods, elements of multigrid, implementation, and some theory.
2. Advanced Tutorial: nonlinear problems, selected applications (Neumann boundary value, anisotropic problems, variable-mesh, and variable-coefficient problems), algebraic multigrid (AMG), multilevel adaptive methods, and finite elements.
3. Computation: error measures, performance measures, programming strategies, simple programming aids, and some tips.
4. Multilevel projection methods: fundamental unification of multilevel concepts.
5. Selected applications.

TOPICS IN NUMERICAL LINEAR ALGEBRA

This class will present an overview of iterative methods for solving large sparse linear systems of equations. The approach will stress two fundamental concepts: polynomial based iteration and preconditioning. Preconditioning, sometimes called matrix splitting, refers to the concept of rearranging the original equations to yield a new system with desirable properties. What properties are desirable? Precisely those that make solution by polynomial methods easier. The methods are called polynomial methods because they attempt to approximate the inverse of a matrix by a polynomial in the matrix itself. The Cayley-Hamilton Theorem tells us that the inverse of a nonsingular matrix can always be expressed as a polynomial in the matrix. Unfortunately, the polynomial described by this theorem is of large degree and unknown. The methods we will examine attempt to find a polynomial of much smaller degree that approximates the inverse. Much of the course will be devoted to this endeavor.

The course will require a basic knowledge in linear algebra. A brief review will be presented at the outset. The course will also require some familiarity with the complex plane. An exposure to functional analysis and the numerical solution of elliptic partial differential equations will be helpful in understanding the motivation for many of preconditioning techniques that will be described.

The class will follow the outline below, touching on each major topic in a depth that will be determined by the pace of the class. The class will involve Matlab workshops and some programming assignments in the Matlab programming language.

No text will be required. The following books may provide useful background material:

• Iterative Methods:
  • Varga, Matrix Iterative Analysis, Prentice-Hall, 1962.
  • Hageman and Young, Applied Iterative Methods, Academic Press, 1981.
  • Golub and Van Loan, Matrix Computations, Johns Hopkins University Press, 1983.
• Numerical Linear Algebra:
  • Gantmacher, Matrix Theory, Vol. I and II, Chelsea Publishing Co., 1960.
  • Strang, Linear Algebra and Its Applications, Academic Press, 1976.
  • Stewart, Introduction to Matrix Computations, Academic Press, 1973.

1. Background Linear Algebra
   1. Vector spaces
      1. Vectors, linear dependence
      2. Subspaces
      3. Norms and inner products
   2. Linear operators
      1. Matrix norms
      2. Eigenvectors and eigenvalues
      3. Jordan decomposition
      4. Cayley-Hamilton Theorem
      5. Singular value decomposition
      6. Four fundamental spaces
   3. Bilinear forms
      1. Riesz Representation Theorem
      2. Adjoint operators
      3. Normal operators
2. Polynomial Methods
   1. One-step methods
      1. Stationary
      2. Nonstationary
   2. Preconditioning/Splitting
      1. General principals
      2. Splittings as preconditionings
      3. Classical examples
   3. Two-step methods
      1. Stationary
         1. Convergence criteria
         2. Parameter choice
      2. Nonstationary
         1. Chebychev method
            1. Symmetric systems
            2. Nonsymmetric systems
      3. Asymptotic limits
   4. K-step methods
      1. Convergence criteria
      2. Parameter choice
   5. Conjugate gradient methods
      1. Symmetric positive definite case
      2. General presentation
      3. Sufficient conditions
      4. Convergence properties
   6. Orthogonal error methods
      1. Existence theorem
      2. S-term recursion
      3. Sufficient conditions
      4. Necessary conditions
      5. Convergence properties
      6. Organizational variants
      7. Equivalence of variants
   7. Projection Methods
      1. Existence Theorems
      2. Boundedness Theorems
      3. Convergence Theorems
      4. Krylov Projection Methods
      5. Semi Krylov Projection Methods
         1. Truncated methods
         2. Restarted Methods
      6. Biconjugate gradient methods
      7. The QMR method
3. Preconditionings
   1. Matrix splittings
      1. General principals
      2. Regular splittings
         1. M-matrices
         2. Spectral bounds
      3. Classical examples
         1. Jacobi
         2. Gauss-Seidel
         3. SOR
         4. ADI
   2. Acceleration of splittings
      1. Symmetric positive definite
      2. Nonsymmetric
   3. Incomplete factorizations
      1. Discrete approximations to elliptic PDEs
      2. General principals
      3. Incomplete Cholesky
         1. Stability
         2. Spectral properties
      4. SSOR
      5. Modified incomplete Cholesky
      6. Shifted incomplete Cholesky
      7. Higher order factorizations
      8. Asymptotic relationship
   4. Polynomial preconditionings
      1. General principals
      2. Symmetric positive definite
         1. Optimal polynomial
         2. Adaptive determination
      3. Symmetric indefinite
         1. Optimal polynomial
         2. Adaptive determination
      4. General case
   5. Equivalent Preconditioning
      1. General principals
      2. Complete multigrid
      3. Partial multigrid
   6. Other preconditionings

Bengt Fornberg

The course will feature two major parts:
      I. Pseudospectral (PS) methods
      II. Radial basis functions (RBFs)

The coverage of the first part will follow the instructor's book "A Practical Guide to Pseudospectral Methods" (Cambridge University Press, 1996) and also "Spectral Methods in Matlab" (SIAM) by L.N. Trefethen. The second part will mainly be based on various research papers.

Brief Description:

Both PS and RBF methods were first introduced about 30 years ago.

PS methods became quickly recognized as often successful, and at times superior alternatives to methodologies such as finite differences and finite elements in several application areas. This included many cases from fluid dynamics, wave motion, and weather forecasting. In this course, we will try to explain how, when, and why the PS approach works, more by means of examples and heuristic illustrations than by rigorous theoretical arguments. A key theme in the presentation will be to exploit the close connection that exists between PS and finite difference methods. This approach to PS methods not only gives many insights, but also provides numerous algorithmic variations which do not appear naturally from more spectral-based approaches to the subject.

The first (and still major) application of RBFs concerns interpolation of data that is irregularly scattered in any number of spatial dimensions. Since the coding effort for RBFs is small, and the computational cost is independent of the number of dimensions and of the regularity of the geometry, it is not surprising that RBFs have recently found extensive use in many applications. In this part of the course, we will first discuss a number of properties of RBF approximations, including their particularly high accuracy in a limit that was previously thought to be impractical for computing. Their application as basis functions for the numerical solution of PDEs - in the style of how trigonometric and orthogonal polynomials are used in PS methods - is of quite recent origin. However, RBFs show great promise in generalizing these highly accurate approaches to entirely general domains.