Finite Element Methods: Parallel-Sparse Statics and Eigen-Solutions

Preface
Disclaimer of Warranty
Acknowledgments
Contents
Chapter 1: A Review of Basic Finite Element Procedures
	1.1 Introduction
	1.2 Numerical Techniques for Solving Ordinary Differential Equations (ODE)
	1.3 Identifying the ``Geometric´´ Versus ``Natural´´ Boundary Conditions
	1.4 The Weak Formulations
	1.5 Flowcharts for Statics Finite Element Analysis
	1.6 Flowcharts for Dynamics Finite Element Analysis
	1.7 Uncoupling the Dynamical Equilibrium Equations
	1.8 One-Dimensional Rod Finite Element Procedures
		1.8.1 One-Dimensional Rod Element Stiffness Matrix
		1.8.2 Distributed Loads and Equivalent Joint Loads
		1.8.3 Finite Element Assembly Procedures
		1.8.4 Imposing the Boundary Conditions
		1.8.5 Alternative Derivations of System of Equations from Finite Element Equations
	1.9 Truss Finite Element Equations
	1.10 Beam (or Frame) Finite Element Equations
	1.11 Tetrahedral Finite Element Shape Functions
	1.12 Finite Element Weak Formulations for General 2-D Field Equations
	1.13 The Isoparametric Formulation
	1.14 Gauss Quadrature
	1.15 Summary
	1.16 Exercises
Chapter 2: Simple MPI/FORTRAN/MATLAB Application
	2.1 Introduction
	2.2 Computing Value of π by Integration
	2.3 Matrix-Matrix Multiplication
	2.4 MPI Parallel I/O
	2.5 Unrolling Techniques
	2.6 Parallel Dense Equation Solvers
		2.6.1 Basic Symmetrical Equation Solver
		2.6.2 Parallel Data Storage Scheme
		2.6.3 Data Generating Subroutine
		2.6.4 Parallel Choleski Factorization
		2.6.5 A Blocked and Cache-Based Optimized Matrix-Matrix Multiplication
			2.6.5.1 Loop Indexes and Temporary Array Usage
			2.6.5.2 Blocking and Strip Mining
			2.6.5.3 Unrolling of Loops
		2.6.6 Parallel ``Block´´ Factorization
		2.6.7 ``Block´´ Forward Elimination Subroutine
		2.6.8 ``Block´´ Backward Elimination Subroutine
		2.6.9 ``Block´´ Error Checking Subroutine
		2.6.10 Numerical Evaluation
		2.6.11 Conclusions
	2.7 A Brief Review of MATLAB Syntax, Sequential, and Parallel Programming
	2.8 Summary
	2.9 Exercises
Chapter 3: Direct Sparse Equation Solvers
	3.1 Introduction
	3.2 Sparse Storage Schemes
	3.3 Three Basic Steps and Reordering Algorithms
		3.3.1 Choleski Algorithm
		3.3.2 LDLT Algorithm
		3.3.3 LDU Algorithm
		3.3.4 Reordering Algorithm
	3.4 Symbolic Factorization with Reordering Column Numbers
		3.4.1 Sparse Symbolic Factorization
		3.4.2 Reordering Column Numbers
	3.5 Sparse Numerical Factorization
	3.6 Super (Master) Nodes (Degrees of Freedom)
	3.7 Numerical Factorization with Unrolling Strategies
	3.8 Forward/Backward Solutions with Unrolling Strategies
	3.9 Alternative Approach for Handling an Indefinite Matrix
	3.10 Conclusions
	3.11 Unsymmetrical Matrix Equation Solver
	3.12 Summary
	3.13 Exercises
Chapter 4: Sparse Assembly Process
	4.1 Introduction
	4.2 A Simple Finite Element Model (Symmetrical Matrices)
	4.3 Finite Element Sparse Assembly Algorithms for Symmetrical Matrices
	4.4 Symbolic Sparse Assembly of Symmetrical Matrices
	4.5 Numerical Sparse Assembly of Symmetrical Matrices
		4.5.1 Key Ideas for Sparse Numerical Assembly Algorithms
	4.6 Step-by-Step Algorithms for Symmetrical Sparse Assembly
	4.7 A Simple Finite Element Model (Unsymmetrical Matrices)
	4.8 Reordering Algorithms
	4.9 Imposing Dirichlet Boundary Conditions
	4.10 Unsymmetrical Sparse Equations Data Formats
	4.11 Symbolic Sparse Assembly of Unsymmetrical Matrices
	4.12 Numerical Sparse Assembly of Unsymmetrical Matrices
	4.13 Step-by-Step Algorithms for Unsymmetrical Sparse Assembly and Unsymmetrical Sparse Equation Solver
	4.14 A Numerical Example
	4.15 Summary
	4.16 Exercises
Chapter 5: Generalized Eigen-Solvers
	5.1 Introduction
	5.2 A Simple Generalized Eigen-Example
		5.2.1 Inverse Iteration Procedure
		5.2.2 Inverse Iterations with Orthonormality Conditions
	5.3 Shifted Eigenproblems
	5.4 Transformation Methods
		5.4.1 Transformation Methods
	5.5 Subspace Iteration Method [5.5]
	5.6 Lanczos Eigensolution Algorithms
		5.6.1 Derivation of Lanczos Algorithms
		5.6.2 Basic Lanczos Algorithms for Eigensolution of Generalized Eigenequation K훟 = λM훟
		5.6.3 Lanczos Eigensolution Error Analysis
		5.6.4 Sturm Sequence Check
		5.6.5 Proving the Lanczos Vectors Are M-Orthogonal
		5.6.6 ``Classical´´ Gram-Schmidt Re-orthogonalization
		5.6.7 Classical Gram-Schmidt Orthogonalization
		5.6.8 Detailed Step-by-Step Lanczos Algorithms
		5.6.9 Detailed Lanczos Algorithms for Eigensolution of Generalized Eigenequation K훟 = λM훟
		5.6.10 Educational Software for Lanczos Algorithms
		5.6.11 Unsymmetrical Eigensolvers
	5.7 Balanced Matrix
	5.8 Reduction to Hessenberg Form
	5.9 QR Factorization
	5.10 Householder QR Transformation
	5.11 ``Modified´´ Gram-Schmidt Re-orthogonalization
		5.11.1 ``Modified´´ Gram-Schmidt Algorithms
	5.12 QR Iteration for Unsymmetrical Eigensolutions
	5.13 QR Iteration with Shifts for Unsymmetrical Eigensolutions
	5.14 Panel Flutter Analysis
		5.14.1 Step-by-Step Procedures for Unsymmetrical Eigenequations
	5.15 Block Lanczos Algorithms
		5.15.1 Details of ``Block Lanczos´´ Algorithms
		5.15.2 Step-by-Step ``Block Lanczos´´ Algorithms
		5.15.3 A Numerical Example for ``Block Lanczos´´ Algorithms
	5.16 Summary
	5.17 Exercises
Chapter 6: Finite Element Domain Decomposition Procedures
	6.1 Introduction
	6.2 A Simple Numerical Example Using Domain Decomposition (DD) Procedures (Classical Substructuring Formulation)
	6.3 Imposing Boundary Conditions on ``Rectangular´´ Matrices
	6.4 How to Construct a Sparse Assembly of ``Rectangular´´ Matrix
	6.5 Mixed Direct-Iterative Solvers for Domain Decomposition
	6.6 Preconditioned Matrix for PCG Algorithm with DD Formulation
		6.6.1 Preconditioned Conjugate Gradient DD Algorithm for Solving
	6.7 Generalized Inverse
	6.8 FETI-D Domain Decomposition Formulation
	6.9 Preconditioned Conjugate Projected Gradient (PCPG) of the Dual Interface Problem
	6.10 Automated Procedures for Computing Generalized Inverse and Rigid Body Motions
	6.11 Numerical Example of a 2D Determinate Truss (21-Bar and 10-Node) by FETI-D Formulation
	6.12 A Preconditioning Technique for Indefinite Linear System
	6.13 FETI-DP Domain Decomposition Formulation
		6.13.1 FETI-DP Step-by-Step Procedures
	6.14 Multilevel Subdomains and Multifrontal Solver
	6.15 Iterative Solution with Successive Right-Hand Sides
		6.15.1 Step-by-Step Iterative Optimization Procedures
		6.15.2 GCR Step-by-Step Algorithms
		6.15.3 Step-by-Step Algorithms to Generate a ``Good´´ Initial Guess for RHS Vectors
	6.16 Summary
	Exercises
Chapter 7: Heuristic Partitioning Algorithm for General Purpose Transportation Networks and Finite Element Meshes
	7.1 Introduction
		7.1.1 Shortest Distance Decomposition Algorithm (SDDA)
		7.1.2 Algorithm Refinements
	7.2 First Proposed SDDA Modification: Link Distance
	7.3 Second Proposed SDDA Modification: Domain Swaps
	7.4 Third Proposed SDDA Modification: The Friend-of-Foe (FoF) Count
	7.5 Numerical Examples
		7.5.1 Anaheim, Real-Life Transportation Network
		7.5.2 Chicago, Real-Life Transportation Network
		7.5.3 Philadelphia, Real-Life Transportation Network
		7.5.4 Three-Dimensional Plus Sign Shape with Tetrahedron Elements
	7.6 Summary
	Exercises
Chapter 8: Parallel Domain Partitioning Shortest Path Algorithms
	8.1 Introduction
	8.2 A Brief Summary of the ``Conventional/Classical´´ Dijkstra Shortest Path Algorithm
	8.3 Development of ``New Sequential and Parallel´´ Dijkstra SP Algorithm with Subdomains
	8.4 A Simple Illustrative (10-Node and 19-Link) Example for Dijkstra SP Algorithm with Three Subdomains
	8.5 Numerical Comparisons Among Sequential and Parallel Dijkstra´s Subdomain Algorithms
	8.6 Summary
	8.7 Acknowledgements
	8.8 Exercises
Chapter 9: Sensitivity Analysis and Optimization with Partitioned Subdomains
	9.1 Introduction
	9.2 Prerequisite Backgrounds
	9.3 Finite Element System Equilibrium Equations with Subdomains
	9.4 Finite Element Sensitivity Analysis with Subdomains
		9.4.1 How to Express δZi in Terms of δb?
		9.4.2 How to Express δZb in Terms of δb?
		9.4.3 How to Express δξ in Terms of δb?
	9.5 Direct Method for Sensitivity (Derivative) Computation
	9.6 Finite Difference Method for Sensitivity (Derivative) Computation
	9.7 Numerical Examples for Sensitivity (Derivative) Computation
	9.8 Sensitivity (Derivative Computation) of Truss Axial Stress Constraints
	9.9 Nonlinear Constraint Optimizer with FMINCON
	9.10 Summary
	9.11 Exercises
Appendix 6.1: Singular Value Decomposition (SVD) and MATLAB Code for Image Application
Appendix 6.2: MATLAB Source Code for Implementing FETI-DP Formulation
Appendix 7.1: Real-Life Philadelphia Network Data
Appendix 7.2: Partitioning Real-Life Philadelphia Network Data into Four Subdomains
Appendix 7.3: MATLAB Code for SDDA, Including FoF, Domain Swapping, and Link Distance
Appendix 8.1: Sequential Computation, Without Using Subdomains (Algorithm #1); for Table 8.7
Appendix 8.2: Embarrassingly Parallel Computation Without Subdomains (Algorithm #2); for Table 8.7
Appendix 8.3: Sequential Computation with Subdomains (Algorithm #3) for Table 8.7
Appendix 8.4: Parallel Computation with Subdomains (Algorithm #4) for Table 8.7
Appendix 8.5: User Manual for Input Data Descriptions
Appendix 8.6: Example Input Data for the 10-node Network, for the Last Algorithm #4 (Parallel with Subdomains)
Appendix 8.7: Sample of Output Data File for the 10-Node Transportation Network
References
Index