## Target Audiences:

• Full-time graduate students in Electrical Engineering and Physics who use computational methods in their dissertation research
• Employees of local high-technology industry who regularly use computational methods and who want practical tools, but not a cookbook

## Concepts/Tools to be Acquired in this Course:

• An understanding of the condition number of a problem. Examples of ill-conditioned problems include floating-point subtraction, finding multiple roots of a polynomial, and solving a system of linear equations with an ill-conditioned coefficient matrix.
• An understanding that algorithms outside the area of linear equations may be ill-conditioned. Examples include upward recursion for Bessel functions of the first kind, and finite-difference algorithms for ordinary differential equations applied outside of the algorithm's region of stability.
• An appreciation of the influences of the nature of the problem to be solved, the properties of floating-point arithmetic, the architecture of available computers, and algorithm design on the feasibility and accuracy of numerical computations.

## Textbooks:

Modern Mathematical Methods for Physicists and Engineers, by Prof. Cantrell, published by Cambridge University Press (ISBN 0-521-59827-3) (Required). There is a UTD Web site for this book with a discussion area.
Selected chapters from Numerical Recipes (in C, FORTRAN or Pascal), by Press, Teukolsky, Vetterling and Flannery (Recommended).

## Syllabus:

1. Floating-point arithmetic:
• Floating-point representations
• General properties
• IEEE-754
• 32-bit and 64-bit formats
• Denormalized numbers
• NaNs and other special values
• Floating-point exception handling
• CRAY
• Rounding methods
• Floating-point operations (+, -, X, /)
• Catastrophic cancellation due to subtraction; introduction to the concept of condition number

2. Evaluation of functions
• Evaluation of polynomials; illustration of catastrophic cancellation
• Evaluation of multiple roots of polynomials (example of ill-conditioned problem; practical approaches)
• Evaluation of partial sums of series
• Alternating vs. same-sign; natural vs. reversed order
• Kahan's algorithm
• Recursive evaluation of functions
• Integral \int_0^1 x(1+x)^{-n} dx
• J_n(x): Miller's method, continued fractions, and more
• Clebsch-Gordan (or 3-j) coefficients

3. Lightning survey of computer architectures
• Von Neumann (model embedded in C and other languages)
• Hierarchical memory; memory interleaving
• CISC
• Pipelining; RISC architectures
• Dependency analysis for computation on a pipelined machine
• Vector architectures
• CRAY
• CONVEX C-series
• Practical aspects of vectorization of scientific and engineering programs
• Parallel architectures
• CONVEX Exemplar
• CRAY (X/MP, Y/MP, C-90)
• Symmetric multiprocessors (Sun, others)
• Practical aspects of parallelization of scientific and engineering programs
• High-performance computing
• Performance analysis, profiling, etc.
• Benchmarking strategies

4. Basic concepts of computational linear algebra (some material is review)
• Vector spaces; dimension and basis; R^n and C^n
• Linear mappings; range and null space; matrices; rank-nullity theorem
• Ordering of array elements in C and FORTRAN
• Loop orderings in matrix multiplication
• Sampling and interpolation as linear mappings
• Systems of linear equations; Gaussian elimination
• LU decomposition
• Gaussian elimination/LU decomposition on pipelined, vector and parallel machines
• Computation of bases of range and null space using LU decomposition
• Diagonal dominance and non-singularity
• Iterative methods
• Basis for iterative methods: The contraction mapping theorem
• Gauss-Seidel iteration
• Successive over-relaxation
• Krylov subspace methods
• Inner products and norms for vectors and matrices
• Orthogonality; QR decomposition
• 3-term recurrence relations for orthogonal polynomials
• Vector norms
• Matrix norms; relation to vector norms
• Condition number of a matrix
• Accuracy of Gaussian elimination
• The singular-value decomposition (SVD)
• Computation of the SVD
• Computation of the fundamental subspaces of a linear mapping A [range(A), null(A), range(A^T), null(A^T)]
• Analysis of ill-conditioned linear systems using the SVD
• Moore-Penrose pseudo-inverse; application to ill-conditioned linear systems
• The linear-least-squares-fitting problem
• Formulation; standard covariance analysis
• Condition number for least-squares fitting; relation to condition number of normal matrix
• Example of an ill-conditioned least-squares problem: Fitting to a polynomial
• The matrix eigenvalue-eigenvector problem
• Bounds on matrix eigenvalues
• Perturbations of the eigenvalue spectrum
• Eigenvalues and eigenvectors of tridiagonal and Hessenberg matrices
• Recursive transformation of a Hermitian matrix to tridiagonal form; Lanczos recursion
• Survey of practical algorithms and packages

5. Numerical integration
• Rectangle rule, trapezoidal rule, and Simpson's rule
• Newton-Cotes methods

6. Finite-difference methods for ordinary differential equations
• Solution of linear, homogeneous difference equations with constant coefficients
• Survey of methods for deriving finite-difference algorithms
• Stability analysis of finite-difference methods
• Euler, backward Euler
• Midpoint
• Trapezoidal
• Midpoint-trapezoidal predictor-corrector
• Runge-Kutta methods
• Methods for stiff equations
• Backward Euler
• Gear's methods
• Methods for linear systems of ODEs in which the coefficient matrix has purely imaginary eigenvalues
• Finite-difference methods as digital filters: Transfer-function analysis
• Boundary-value problems for ODEs

7. Numerical methods for partial differential equations
• First-order quasilinear PDEs
• Method of characteristics
• Burgers' equation
• Shock waves and characteristics
• Stability analysis of explicit FD methods: Transfer function, von Neumann's method, matrix method
• Weighted-differencing methods; upwind differencing
• Implicit differencing schemes
• Classification of second-order quasilinear PDEs
• Hyperbolic PDEs
• Method of characteristics (standard formulation)
• Method of characteristics (matrix formulation)
• Finite-difference schemes
• Dispersion-relation analysis of finite-difference schemes
• Parabolic PDEs
• General approach: Discretization in space, leading to a system of ODEs in time
• Explicit methods; stability analysis; stiffness of resulting system of ODEs
• Implicit methods; stability analysis
• Crank-Nicholson
• Stiff methods
• Incorporation of derivative boundary conditions in matrix method of stability analysis
• Stability analysis using transfer functions
• Predictor-corrector methods for nonlinear parabolic PDEs
• Operator-splitting methods
• Absorbing boundary conditions
• Application of digital filtering to nonlinear parabolic PDEs
• The paraxial-wave equation
• Spectral and pseudo-spectral methods
• Case study of laser-beam propagation in a nearly-resonant medium
• Bidirectional propagation
• Survey of finite-element methods
• Elliptic PDEs
• Finite-difference schemes
• Iterative methods for solving linear systems
• Jacobi, Gauss-Seidel
• Successive over-relaxation