Scientific Computing - Numerical Analysis PhD Qualifying Exam

The Numerical Analysis PhD Qualifying Examination (NA Qual) is intended to determine whether a student is qualified to begin research toward a PhD dissertation in the general area of numerical analysis. The NA Qual also enforces a breadth requirement in numerical analysis. The format is a 90-minute oral examination in which a committee of three faculty members asks the student questions on any topic listed in the examination syllabus. The student is expected to be able to supply any requested details, such as proofs and derivations, on the whiteboard without consulting any notes or references.

Prior to taking the Qual, the student must submit a written statement (one to two pages) describing his or her academic background, technical interests, experience, intended area of research specialization, and general academic plans. The student begins the examination with a brief (five to ten minute) oral summary of his or her research interests. The committee may ask a few questions specific to the student's stated interests, but by far the bulk of the examination consists of general questions drawn from the material listed in the examination syllabus.

There are numerous facts and techniques that should be known by every PhD graduate who claims a research interest in numerical analysis. A 90-minute examination is inadequate to test all of these, but a reasonable subset is to focus on the material typically covered in the courses CS 450 and CS 555, which serves as the basis for the detailed examination syllabus. Note that the student is responsible for all of the topics in the examination syllabus, even if some may have been omitted from a particular offering of CS 450 or 555.

You should take both CS 450 and CS 555 unless you have already taken equivalent courses elsewhere and done well in them. You should obtain several intermediate-level books on numerical analysis and use them to flesh out your knowledge of the topics listed in the syllabus (specific suggestions are given in the accompanying reading list). There is often more than one way to express various definitions, theorems, and algorithms, and you should find ways of expressing them that you are comfortable with. You should confer with your faculty advisor, who can give you a realistic assessment of your potential as well as specific advice on exam preparation. You should practice as much as possible by answering the sample questions and questions from previous NA Qual exams, and by conducting mock quals with fellow students and/or your advisor. The latter will give you experience answering questions "on your feet" in a setting that approximates that of the actual exam, and will help you become more comfortable with the exam format.

The student is expected to have a general knowledge of the following topics at about the level covered in the lectures, lecture notes, textbooks, and prerequisites for CS 450 and CS 555. For each topic (concept, theorem, problem, algorithm, etc.) listed, standard questions that might be asked include its definition, existence, uniqueness, characterization, derivation, proof, applicability, sensitivity, stability, accuracy, convergence, computational complexity, etc., as may be relevant.

• General error analysis: well-posed problems, problems vs. algorithms, data error vs. computational error, forward error vs. backward error, conditioning of a problem, stability of an algorithm.
• Finite-precision computation: floating-point numbers, rounding rules, machine precision, floating-point arithmetic, cancellation.
• Operation counts, "big O" notation.

• Mathematical background: vector spaces, subspaces, linear independence, rank, dimension, span, basis, null space, determinant, existence and uniqueness of solutions to linear systems, permutation matrices, transpose, conjugate transpose, symmetric matrices, Hermitian matrices, partitioned matrices.
• Norms and conditioning: vector norm, matrix norm, condition number of a matrix, error bounds for solutions to linear systems, residual vs. error.
• Gaussian elimination: LU factorization, permutations, partial pivoting, complete pivoting, growth factor, scaling, diagonal dominance, iterative refinement, Gauss-Jordan elimination, rank-one updating.
• Symmetric matrices: symmetric positive definite matrices, Cholesky factorization, symmetric indefinite systems.
• Sparse linear systems: band matrices, sparse storage schemes, graph of a matrix, graph interpretation of elimination, fill, reordering for sparsity, nested dissection, minimum degree.
• Stationary iterative methods: spectral radius, convergence rate, Jacobi, Gauss-Seidel, and SOR methods.
• Conjugate gradient method: finite convergence, optimality, conjugacy of search directions.

• Mathematical background: orthogonality, idempotence, orthogonal projectors, existence and uniqueness of least squares solutions to (not necessarily square) linear systems, normal equations.
• Orthogonalization methods: orthogonal matrices, Householder reflections, Givens rotations, QR factorization, classical and modified Gram-Schmidt orthogonalization.
• Singular value decomposition: rank, Euclidean norm, condition number, and pseudoinverse of a matrix in terms of its SVD; orthonormal bases, lower-rank approximation.
• Algebraic Eigenvalue Problems
• Mathematical background: eigenvalues, characteristic polynomial, Cayley-Hamilton Theorem, algebraic and geometric multiplicity, defective matrix, diagonalizable matrices, normal matrices, invariant subspaces, block triangular matrices, Schur form, real Schur form, Jordan form, Gershgorin Theorem.
• Power method, inverse iteration, Raleigh quotient iteration, deflation.
• QR iteration: simultaneous iteration, orthogonal iteration, QR iteration, reduction to Hessenberg or tridiagonal form, shifts.
• Krylov subspace methods: Lanczos iteration, Arnoldi iteration
• Jacobi iteration

• Mathematical background: Intermediate Value Theorem, Inverse Function Theorem, Contraction Mapping Theorem, coerciveness, convexity, gradient vector, Hessian matrix, optimality conditions.
• Convergence rates, order of convergence, simple vs. multiple root.
• Single equations: bisection, fixed-point iteration, Newton's method, secant method, inverse interpolation, safeguarded methods.
• Systems of equations: fixed-point iteration, Jacobian matrix, Newton's method, Broyden's method, robust (damped or trust-region) Newton-like methods.
• One-dimensional optimization: golden section search, successive parabolic interpolation, Newton's method, safeguarded methods.
• Multidimensional unconstrained optimization: steepest descent method, Newton's method, quasi-Newton methods, conjugate gradient method, line search, trust-region methods.

• Mathematical background: existence and uniqueness of interpolant.
• Polynomial interpolation: Vandermonde matrix, Lagrange and Newton forms, divided differences, Hermite interpolation, convergence and error bound for polynomial interpolation of a continuous function, Runge phenomenon, Chebyshev points, Taylor polynomial.
• Piecewise polynomial interpolation: Hermite cubic interpolation, splines, cubic spline interpolation, natural cubic spline.
• Trigonometric interpolation: discrete Fourier transform, FFT algorithm
• Orthogonal polynomials: function spaces, inner products, orthogonality, Gram-Schmidt orthogonalization, three-term recurrence, Legendre polynomials, Chebyshev polynomials.
• Polynomial approximation: Weierstass Approximation Theorem, best uniform approximation, least squares approximation.

• Mathematical background: Riemann sums, existence of Riemann integral, ill-posedness of differentiation.
• Numerical quadrature: interpolatory quadrature, method of undetermined coefficients, moment equations, Newton-Cotes quadrature, midpoint rule, trapezoid rule, Simpson's rule, Gaussian quadrature, composite quadrature, adaptive quadrature.
• Extrapolation methods: Richardson extrapolation, Romberg integration
• Numerical differentiation: conditioning, interpolation, smoothing, finite difference approximations.

• Mathematical background: order, reduction to first order, autonomous systems, stability of solutions, linear homogeneous systems with constant coefficients, Jacobian matrix for a nonlinear system.
• Basic numerical methods: Euler's method, backward Euler method, trapezoid method.
• Accuracy and stability: truncation error, local error, global error, order of accuracy, stability of numerical method, scalar test problem, convergence, difference equations, root condition, local error estimation, step size control.
• Multistep methods: explicit and implicit Adams methods, predictor-corrector methods, backward differentiation formulas, solution of implicit equations.
• Taylor series, Runge-Kutta, and extrapolation methods.

• Mathematical background: fundamental matrix, Green's function, dichotomy.
• Shooting method
• Finite difference method
• Collocation method
• Galerkin method

• Mathematical background: Laplace, Poisson, and Helmholtz equations; essential (Dirichlet) and natural (Neumann) boundary conditions.
• Weighted residual methods: weak form, trial and test functions; Divergence Theorem and integration by parts, Rayleigh-Ritz-Galerkin method, stiffness matrix and load vector.
• Finite element methods: linear and quadratic finite elements, shape functions, basis functions, quadrature, assembly.
• Finite difference methods: five-point stencil, symmetry and positive definiteness, fast direct solvers (e.g., cyclic reduction).

• Mathematical background: heat equation in one and two space dimensions, boundary conditions, advection-diffusion equation, Burgers' equation, ill-posedness of backward heat equation.
• Numerical methods: theta method, Crank-Nicolson method, method of lines, ADI.
• Accuracy and stability: local and global truncation error, Fourier (von Neumann) stability analysis.
• Linearization of nonlinear discrete equations by Newton's method.

• Mathematical background: classification of first-order systems and second-order single equations, characteristics, domain of dependence.
• Conservation laws: advection equation, wave equation, inviscid Burgers' equation.
• Finite difference methods: consistency, stability, convergence, Lax Equivalence Theorem, Fourier (von Neumann) stability analysis.

The following reading list contains many books, but you aren't expected to read all of them! Typically, you will need to read only one or two books in any given category. The point of this list is to provide a wide variety of choices so that you can find sources you are comfortable with for learning or reviewing all of the material on the exam syllabus. Some items are highlighted in red because they offer especially concise coverage of requisite topics at about the right level expected for the exam, so these are a good place to start. You may also need to consult other references, however, to flesh out some topics in greater depth or detail, but you should be aware that many of these references go far beyond the minimum you are expected to know for the exam.

A good general numerical analysis text will cover perhaps half to three-quarters of the material you need to know for the exam, so this is the obvious place to begin your reading. The book by Heath is comprehensive, concise, and up to date, and is the textbook used for CS 450, so it is a good candidate to read (or reread) for exam preparation. It contains no formal proofs, however, so you may want additionally to consult one or two of the more mathematical texts listed here.

• K. Atkinson, An Introduction to Numerical Analysis, 2nd ed., Wiley, 1989.
• G. Dahlquist and A. Bjorck, Numerical Methods in Scientific Computing, SIAM, 2008.
• P. Deuflhard and A. Hohmann, Numerical Analysis in Modern Scientific Computing, 2nd ed., Springer, 2003.
• W. Gautschi, Numerical Analysis: An Introduction, Birkhauser, 1997.
• M. T. Heath, Scientific Computing: An Introductory Survey, 2nd ed., McGraw-Hill, 2002.
• E. Isaacson and H. B. Keller, Analysis of Numerical Methods, Dover, 1994 (reprint of 1966 ed.).
• D. Kincaid and W. Cheney, Numerical Analysis: Mathematics of Scientific Computing, 3rd ed., Brooks/Cole, 2002.
• R. Kress, Numerical Analysis, Springer, 1998.
• J. M. Ortega, Numerical Analysis: A Second Course, SIAM, 1990 (reprint of 1972 ed.).
• A. Quarteroni, R. Sacco, and F. Saleri, Numerical Mathematics, Springer, 2000.
• M. Schatzman, Numerical Analysis: A Mathematical Introduction, Oxford, 2002.
• H. R. Schwarz, Numerical Analysis: A Comprehensive Introduction, Wiley, 1989.
• J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, 3rd ed., Springer, 2002.
• E. Suli and D. Mayers, An Introduction to Numerical Analysis, Cambridge, 2003.

These topics are covered adequately in most general texts, including Heath, but the following references provide further details and examples on error analysis and floating-point arithmetic.

• D. Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys, 18(1):5-48, 1991.
• N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002.
• M. L. Overton, Numerical Computing with IEEE Floating Point Arithmetic, SIAM, 2001.

There are many good books on this topic, from the relatively concise textbook by Trefethen and Bau to the encyclopedic treatise by Golub and Van Loan. Trefethen and Bau goes very little beyond the coverage in Heath, but offers a distinct perspective that will enrich your knowledge. It would also be a good idea to consult a book specifically on iterative methods for linear systems, several of which are listed here.

• Z. Bai, et al., Templates for the Solution of Algebraic Eigenvalue Problems, SIAM, 2000.
• R. Barrett, et al., Templates for the Solution of Linear Systems, SIAM, 1994.
• A. Bjorck, Numerical Methods for Least Squares Problems, SIAM, 1996.
• J. W. Demmel, Applied Numerical Linear Algebra, SIAM, 1997.
• G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins, 1996.
• A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, 1997.
• C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995.
• B. N. Parlett, The Symmetric Eigenvalue Problem, SIAM, 1998 (reprint of 1980 ed.).
• Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003.
• G. W. Stewart, Matrix Algorithms, Vol. I: Basic Decompositions, SIAM, 1998; Vol. II: Eigensystems, SIAM, 2001
• L. N. Trefethen and D. Bau, Numerical Linear Algebra, SIAM, 1997.
• H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge, 2003
• D. S. Watkins, Fundamentals of Matrix Computations, 2nd ed., Wiley, 2002

The books by Kelley provide concise coverage, but with greater mathematical detail than most general NA texts, of everything you need to know in this category. The other references listed here are excellent, but contain either greater depth (e.g., Ortega and Rheinboldt) or more topics (e.g., constrained optimization) than required for the exam.

• J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1996 (reprint of 1983 ed.).
• P. E. Gill, W. Murray and M. H. Wright, Practical Optimization, Academic, 1981.
• C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995.
• C. T. Kelley, Iterative Methods for Optimization, SIAM, 1999.
• C. T. Kelley, Solving Nonlinear Equations with Newton's Method, SIAM, 2003.
• J. Nocedal and S. J. Wright, Numerical Optimization, Springer, 1999.
• J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic, 1970.

These topics are adequately covered in many general NA texts, but it may nevertheless be a good idea to gain additional depth and details by consulting a more specialized book, such as Phillips. Note that Heath covers interpolation but not approximation of functions.

• P. J. Davis, Interpolation and Approximation, Dover, 1975 (reprint of 1963 ed.).
• C. de Boor, A Practical Guide to Splines, 2nd ed., Springer, 1984.
• W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Oxford, 2004
• G. M. Phillips, Interpolation and Approximation by Polynomials, Springer, 2003.
• T. J. Rivlin, An Introduction to the Approximation of Functions, Dover, 1981 (reprint of 1969 ed.).

Again, these topics are adequately covered in many general NA texts, but it may nevertheless be a good idea to gain additional depth and details by consulting a more specialized book, though all of the books listed go well beyond the minimum you will need.

• P. J. Davis and P. Rabinowitz, Methods of Numerical Integration, 2nd ed., Academic, 1984.
• G. Evans, Practical Numerical Integration, Wiley, 1993.
• A. R. Krommer and C. W. Ueberhuber, Computational Integration, SIAM, 1998.

Although this topic is covered adequately for purposes of the exam in many general NA texts, it is probably a good idea to go somewhat beyond that level by reading a more specialized source, such as Ascher and Petzold or Iserles, both of which are reasonably concise (but still go somewhat beyond the minimum you need).

• U. M. Ascher and L. R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, 1998
• J. C. Butcher, Numerical Methods for Ordinary Differential Equations, 2nd ed., Wiley, 2003.
• P. Deuflhard and F. Bornemann, Scientific Computing with Ordinary Differential Equations, Springer, 2002
• J. R. Dormand, Numerical Methods for Differential Equations, CRC Press, 1996.
• A. Iserles, A First Course in the Numerical Analysis of Differential Equations, Cambridge, 1996.
• L. F. Shampine, Numerical Solution of Ordinary Differential Equations, Chapman & Hall, 1994.

This is the topic on the exam syllabus that is by far the least well covered in general NA texts (indeed, some omit it entirely), so you will definitely need to do some additional reading here. Concise, minimally adequate sources are Morton and Mayers for finite difference methods and Johnson for finite element methods, both of which have been used as texts for CS 555. Note that Johnson's book has been superseded by the more recent book by Eriksson et al., but the latter is twice as long. Another attractive alternative is the book by Iserles, which covers both ODEs and PDEs (both finite difference and finite element methods) from a single, coherent perspective, and is relatively concise considering its breadth of coverage.

• U. M. Ascher, Numerical Methods for Evolutionary Differential Equations, SIAM, 2008.
• O. Axelsson and V. A. Barker, Finite Element Solution of Boundary Value Problems, SIAM, 2001 (reprint of 1984 ed.).
• D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, 3rd ed., Cambridge, 2007.
• S. C. Brenner and R. Scott, The Mathematical Theory of Finite Element Methods, 3rd ed., Springer, 2008.
• K. Eriksson, D. Estep, P. Hansbo and C. Johnson, Computational Differential Equations, Cambridge, 1996.
• M. S. Gockenbach, Partial Differential Equations: Analytical and Numerical Methods, SIAM, 2002.
• M. S. Gockenbach, Understanding and Implementing the Finite Element Method, SIAM, 2006.
• A. Iserles, A First Course in the Numerical Analysis of Differential Equations, Cambridge, 1996.
• C. Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover, 2009 (reprint of 1987 ed.).
• H. P. Langtangen, Computational Partial Differential Equations, 2nd ed., Springer, 2003.
• R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations, SIAM, 2007.
• K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations, 2nd ed., Cambridge, 2005.
• A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations, 2nd ed., Springer 1997.
• J. C. Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd ed., SIAM, 2004.
• J. W. Thomas, Numerical Partial Differential Equations, Vol. 1: Finite Difference Methods, Springer, 1995.
• J. W. Thomas, Numerical Partial Differential Equations, Vol. 2: Conservation Laws and Elliptic Equations, Springer, 1999.

Research in numerical analysis generally relies on a substantial knowledge of mathematics and mathematical techniques. The relevant mathematical background material is typically learned through a combination of courses, books, and experience. Listed here are the major mathematical topics with which you should be reasonably familiar, along with (highly selective) suggested references for learning or reviewing them at an appropriate level for the exam. For convenience, mathematics courses at UIUC that cover each topic are also listed here. This does not mean that you are required to take these courses (or their equivalent elsewhere) or read these specific references in order to pass the exam. However, mathematical questions that are directly relevant to numerical methods (e.g., boundary conditions and well-posedness for PDEs, integration by parts, divergence theorem, etc.) may be asked on the exam, and you should prepare accordingly.

• Linear Algebra (Math 415 or 418): vector spaces, linear independence, rank, bases, orthogonality, projectors
  • G. Strang, Introduction to Linear Algebra, 3rd ed., Wellesley-Cambridge Press, 2003.
• Matrix Theory (Math 415 or 418): eigenvalues, multiplicity, Schur form, Jordan form
  • C. D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, 2000.
  • R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge, 1985.
• Vector Analysis (Math 481): gradient, divergence, curl, divergence theorem
  • P. C. Matthews, Vector Calculus, Springer, 1998.
• Ordinary Differential Equations (Math 441 or 550): IVPs, BVPs, existence, uniqueness, stability
  • R. M. M. Mattheij and J. Molenaar, Ordinary Differential Equations in Theory and Practice, SIAM, 2002 (reprint of 1996 ed.).
• Partial Differential Equations (Math 442 or 553): classification, initial/boundary conditions, characteristics
  • W. A. Strauss, Partial Differential Equations, An Introduction, Wiley, 1992.
  • A. Tveito and R. Winther, Introduction to Partial Differential Equations: A Computational Approach, Springer, 1998.
• Real Analysis (Math 444, 447, or 540/541): limits, continuity, differentiability, integrability
  • S. Abbott, Understanding Analysis, Springer, 2001.
  • D. Estep, Practical Analysis in One Variable, 2002.
• Functional Analysis (Math 546): Banach spaces, Hilbert spaces, Sobolev spaces, linear operators, linear functionals
  • K. Atkinson and W. Han, Theoretical Numerical Analysis: A Functional Analysis Framework, Springer, 2001.
  • K. Saxe, Beginning Functional Analysis, Springer, 2002.
• Applied Mathematics (Math 498, 556/557 or TAM 541/542):
  • G. Strang, Introduction to Applied Mathematics, Wellesley-Cambridge Press, 1986.
  • G. Strang, Computational Science and Engineering, Wellesley-Cambridge Press, 2007.