Summer 2006
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:
- 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
- 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
- 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
- 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
- Numerical integration
- Rectangle rule, trapezoidal rule, and Simpson's rule
- Newton-Cotes methods
- Practical adaptive-quadrature algorithms
- Gaussian quadrature methods
- 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
- Adams-Moulton methods
- Adams-Bashforth 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
- 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
- Conjugate gradients
- Operator-splitting methods
- Multigrid methods
- Pseudorandom-number generators
- The FFT