CPS615 Gauss Seidel Finite Element Methods and Conjugate Gradient

This discusses sequential and parallel Gauss Seidel and Jacobi Iteration aThis is followed by an elementary discussion of Finite Element Methods applied to Laplace's equation in two dimensions. This motivates the following detailed account of Conjugate Gradient method including parallelism and analogies with optimization http://www.npac.syr.edu/users/gcf/CPS615FEM95/index.html

• Finite and Infinite Dimensional Matrices as Operators
• d/dx as an Operator and Its Scalar Products
• d/dx as a Hermitean Operator
• The Laplacian as a (Matrix) Operator
• Mapping of Function Spaces to a Finite Number of Dimensions
• Mathematical and Pseudo Code Form of Gauss Seidel Iteration Method
• Mathematical (Matrix) Form of Gauss Seidel
• Parallelism in Gauss-Seidel Iteration
• Matrix Example Stencil
• Matrix---Wavefront Parallelism for Gauss Seidel
• The Red-Black Two Phase Parallel Gauss Seidel Iteration
• Analysis of Parallel Red Black Gauss Seidel
• Eigenvalues of Gauss Seidel Iteration Matrix
• Comparison of Convergence of Gauss-Seidel and Jacobi Iteration
• Successive Overrelaxation Iteration Method (SOR)
• Convergence of SOR Compared to Jacobi and Gauss Seidel
• Estimate of Over Relaxation Parameter
• Pseudo Code for SOR---Successive Over Relaxation
• Integral Formulation of Finite Element Method
• Variation in Integral
• Equivalence of Integral and Differential Formulation of Laplace's Equation
• Discretization of Integral
• Triangular Elements in Two Dimensions
• Example for Two-Dimensional Triangular Elements
• Bilinear Form of Integral with Triangular Elements
• Formula for Stiffness Matrix Element
• Finite Element Equations
• Structure of Stiffness Matrix and Its Assembly
• Conditions on Triangulation
• Introduction to Poor Person's Conjugate Gradient
• Conjugate Gradient Iteration for Quadratic Form
• Conjugate Gradient and Method of Steepest Descent
• Conjugate Gradient for Finite Element Problems
• Poor Person's Conjugate Gradient and Eigenvalues of Matrix
• Diagonalization of Quadratic Form
• Diagonalization of Conjugate Gradient Equations
• Convergence of Conjugate Gradient in Diagonalized Form
• Clarification of Eigenvalue Analysis for Conjugate Gradient and Jacobi Iteration
• Intuitive Description of Poor Person's Conjugate Gradient Algorithm
• Improvement of Poor Person's Conjugate Gradient with Orthonormal Iteration
• Full Conjugate Gradient Algorithm
• Overview of Parallelism in Conjugate Gradient
• Parallel Issues in Calculation of Matrix Elements
• Scalar Products in Parallel Conjugate Gradient
• Preconditioning in Conjugate Gradient
• Convergence of Conjugate Gradient