Glossary#
adjacency matrix (§ 7.1) Matrix whose nonzero entries show the links between nodes in a graph.
adjoint (§ 2.2) Conjugate transpose of a complex matrix.
advection equation (§ 12.1) Archetypical PDE of hyperbolic type, representing transport phenomena.
algorithm (§ 1.3) List of instructions for transforming data into a result.
Arnoldi iteration (§ 8.4) Stable algorithm for finding orthonormal bases of nested Krylov subspaces.
asymptotic (§ 2.5) Relationship indicating that two functions have the same leading behavior in some limit.
backward error (§ 1.4) Change to the input of a problem required to produce the result found by an inexact algorithm.
backward substitution (§ 2.3) Systematic method for solving a linear system with an upper triangular matrix.
bandwidth (§ 2.9) The number of diagonals around the main diagonal that have nonzero elements.
barycentric formula (§ 9.2) Computationally useful expression for the interpolating polynomial as a ratio of rational terms.
big-O (§ 2.5) Relationship indicating that one function is bounded above by a multiple of another in some limit.
boundary-value problem (§ 10.1) A differential equation with which partial information about the solution is given at multiple points on the boundary of the domain.
cardinal function (§ 5.1) Interpolating function that is 1 at one node and 0 at all the others.
Cholesky factorization (§ 2.9) Symmetrized version of LU factorization for SPD matrices.
collocation (§ 10.4) Solution of a differential equation by imposing it approximately at a set of nodes.
condition number (§ 1.2) Ratio of the size of change in the output of a function to the size of change in the input that produced it.
cubic spline (§ 5.3) Piecewise cubic function with two globally continuous derivatives, most often used for interpolation or approximation.
diagonalizable (§ 7.2) Matrix that admits an eigenvalue decomposition. Also known as nondefective.
differentiation matrix (§ 10.3) Matrix mapping a vector of function values to a vector of approximate derivative values.
Dirichlet condition (§ 10.1) Boundary condition specifying the value of the solution.
dominant eigenvalue (§ 8.2) Eigenvalue with the largest modulus (absolute value, in the real case).
double precision (§ 1.1) Typical standard in floating-point representation, using 64 bits to achieve about 16 decimal significant digits of precision.
eigenvalue (§ 7.2) Scalar \(\lambda\) such that \(\mathbf{A}\mathbf{x} = \lambda \mathbf{x}\) for a square matrix \(\mathbf{A}\) and nonzero vector \(\mathbf{x}\).
eigenvalue decomposition (EVD) (§ 7.2) Expression of a square matrix as the product of eigenvector and diagonal eigenvalue matrices.
eigenvector (§ 7.2) Vector for which the action of a matrix is effectively one-dimensional.
Euler’s method (§ 6.2) Prototype of all IVP solution methods, obtained by assuming constant derivatives for the solution over short time intervals.
evolutionary PDE (§ 11.1) A partial differential equation in which one of the independent variables is time or a close analog.
extrapolation (§ 5.6) Use of multiple discretization values to cancel out leading terms in an error expansion.
finite difference (§ 5.4) Linear combination of function values that approximates the value of a derivative of the function at a point.
finite element method (FEM) (§ 10.6) Use of piecewise integration to pose a linear system of equations for the approximate solution of a boundary-value problem.
fixed point iteration (§ 4.2) Repeated application of a function in hopes of converging to a fixed point.
fixed point problem (§ 4.2) Finding a value of a given function where the input and output values are the same; equivalent to rootfinding.
floating-point numbers (§ 1.1) A finite set that substitutes for the real numbers in machine calculations. Denoted by \(\mathbb{F}\).
flops (§ 2.5) Arithmetic operations on floating-point numbers, often counted as a proxy for computer runtime.
forward substitution (§ 2.3) Systematic method for solving a linear system with a lower triangular matrix.
Frobenius norm (§ 2.7) Matrix norm computed by applying the vector 2-norm to a vector interpretation of the matrix.
Gauss–Newton method (§ 4.7) Generalization of Newton’s method for nonlinear least squares.
Gaussian elimination (§ 2.4) Use of row operations to transform a linear system to an equivalent one in triangular form.
generating polynomials (§ 6.6) A pair of polynomials whose coefficients match those of a multistep method for IVPs.
global error (§ 6.2) Error made by an IVP method over the entire time interval of the solution.
GMRES (§ 8.5) Iterative solution of a linear system through stable least-squares solutions on nested Krylov subspaces.
graph (§ 7.1) Representation of a network as a set of nodes and edges.
hat functions (§ 5.2) Cardinal functions for piecewise linear interpolation.
heat equation (§ 11.1) Archetypical parabolic PDE that describes diffusion.
hermitian (§ 7.4) Combination of transpose and elementwise complex conjugation. Also describes a matrix that equals its own hermitian.
hermitian positive definite (HPD) (§ 7.4) Matrix that is hermitian with strictly positive eigenvalues; complex variant of symmetric positive definite.
identity matrix (§ 2.2) Matrix with ones on the diagonal and zeros elsewhere, acting as the multiplicative identity.
ill-conditioned (§ 1.2) Exhibiting a large condition number, indicating high sensitivity of a result to changes in the data.
implicit (§ 6.6) Formula that defines a quantity only indirectly, e.g., as the solution of a nonlinear equation.
induced matrix norm (§ 2.7) Norm computed using the interpretation of a matrix as a linear operator.
initial-value problem (IVP) (§ 6.1, § 6.3) An ordinary differential equation (possibly vector-valued) together with an initial condition.
inner product (§ 9.4) Scalar or dot product of a pair of vectors, or its extension to a pair of functions.
interpolation (§ 2.1, § 5.1) Construction of a function that passes through a given set of data points.
inverse iteration (§ 8.3) Subtraction of a shift followed by matrix inversion, used in power iteration to transform the eigenvalue closest to a target value into a dominant one.
Jacobian matrix (§ 4.5) Matrix of first partial derivatives that defines the linearization of a vector-valued function.
Kronecker product (§ 13.3) Alternative type of matrix multiplication useful for problems on a tensor-product domain.
Krylov subspace (§ 8.4) Vector space generated by powers of a square matrix that is often useful for reducing the dimension of large problems.
Lagrange formula (§ 9.1) Theoretically useful expression for an interpolating polynomial.
Lanczos iteration (§ 8.6) Specialization of the Arnoldi iteration to the case of a hermitian (or real symmetric) matrix.
Laplace equation (§ 13.3) Archetypical elliptic PDE describing a steady state.
linear convergence (§ 4.2) Sequence in which the difference between sequence value and limit asymptotically decreases by a constant factor at each term, making a straight line on a log-linear graph.
linear least-squares problem (§ 3.1) Minimization of the 2-norm of the residual for an overdetermined linear system.
local truncation error (§ 6.2, § 6.6) Discretization error made in one time step of an IVP solution method.
LU factorization (§ 2.4) Factorization of a square matrix into the product of a unit lower triangular matrix and an upper triangular matrix.
machine epsilon (§ 1.1) Distance from 1 to the next-largest floating-point number. Also called unit roundoff or machine precision, though the usages are not consistent across different references.
matrix condition number (§ 2.8) Norm of the matrix times the norm of its inverse, equivalent to the condition number for solving a linear system.
method of lines (§ 11.2) Solution technique for partial differential equations in which each independent variable is discretized separately.
multistep (§ 6.6) Formula using information over more than a single time step to advance the solution.
Neumann condition (§ 10.1) Boundary condition specifying the derivative of the solution.
Newton’s method (§ 4.3) Rootfinding iteration that uses the linearization of the given function in order to define the next root approximation.
nodes (§ 5.1) Values of the independent variable where an interpolant’s values are prescribed.
nonlinear least-squares problem (§ 4.7) Minimization of the 2-norm of the residual of a function that depends nonlinearly on a vector.
norm (§ 2.7) Means of defining the magnitude of a vector or matrix.
normal (§ 7.2) Matrix that has a unitary eigenvalue decomposition.
normal equations (§ 3.2) Square linear system equivalent to the linear least-squares problem.
numerical integration (§ 5.6) Estimation of a definite integral by combining values of the integrand, rather than by finding an antiderivative.
one-step IVP method (§ 6.2) IVP solver that uses information from just one time level to advance to the next.
ONC matrix (§ 3.3) Matrix whose columns are orthonormal vectors.
order of accuracy (§ 5.5, § 5.6, § 6.2, § 6.6) Leading power of the truncation error as a function of a discretization size parameter.
orthogonal vectors (§ 3.3) Nonzero vectors that have an inner product of zero.
orthogonal matrix (§ 3.3) Square ONC matrix, i.e., matrix whose transpose is its inverse.
orthogonal polynomials (§ 9.4) Family of polynomials whose distinct members have an integral inner product equal to zero, as with Legendre and Chebyshev polynomials.
orthonormal vectors (§ 3.3) Vectors that are both mutually orthogonal and all of unit 2-norm.
outer product (§ 2.4) Multiplication of two vectors resulting in a rank-1 matrix.
overdetermined (§ 3.1) Characterized by having more constraints than available degrees of freedom.
piecewise linear (§ 5.2) Function that is linear between each consecutive pair of nodes, but whose slope may jump at the nodes.
PLU factorization (§ 2.6) LU factorization with row pivoting.
power iteration (§ 8.2) Repeated application of a matrix to a vector, followed by normalization, resulting in convergence to an eigenvector for the dominant eigenvalue.
preconditioning (§ 8.8) Use of an approximate inverse to improve the convergence rate of Krylov iterations for a linear system.
pseudoinverse (§ 3.2) Rectangular matrix that maps data to solution in the linear least-squares problem, generalizing the matrix inverse.
QR factorization (§ 3.3) Representation of a matrix as the product of an orthogonal and an upper triangular matrix.
quadratic convergence (§ 4.3) Sequence in which the difference between sequence value and limit asymptotically decreases by a constant times the square of the preceding difference.
quasi-Newton methods (§ 4.6) Rootfinding methods that overcome the issues of Jacobian computation and lack of global convergence in Newton’s method.
quasimatrix (§ 9.4) Collection of functions (such as orthogonal polynomials) that have algebraic parallels to columns of a matrix.
Rayleigh quotient (§ 7.4) Function of vectors that equals an eigenvalue when given its eigenvector as input.
reduced QR factorization See thin QR.
reduced SVD See thin SVD.
residual (§ 2.8, § 4.1) For a linear system, the difference between \(\mathbf{b}\) and \(\mathbf{A}\tilde{\mathbf{x}}\) for a computed solution approximation \(\tilde{\mathbf{x}}\). More generally, the actual value of a quantity that is made zero by an exact solution.
restarting (§ 8.5) Technique used in GMRES to prevent the work per iteration and overall storage from growing uncontrollably.
rootfinding problem (§ 4.1) Finding the input value for a given function which makes that function zero.
row pivoting (§ 2.6) Reordering rows during LU factorization to ensure that the factorization exists and can be computed stably.
Runge phenomenon (§ 9.3) Manifestation of the instability of polynomial interpolation at equally spaced nodes as degree increases.
Runge–Kutta (§ 6.4) One-step method for IVPs that evaluates the derivative of the solution more than once to advance a single step.
secant method (§ 4.4) Scalar quasi-Newton method that uses a secant line rather than a tangent line to define a root estimate.
shooting (§ 10.2) Unstable technique for solving a boundary-value problem in which an initial value is sought for by a rootfinding algorithm.
simple root (§ 4.1) Root of a function at which the derivative of the function is nonzero.
singular value decomposition (SVD) (§ 7.3) Expression of a matrix as a product of two orthogonal/unitary matrices and a nonnegative diagonal matrix.
sparse (§ 2.9, § 8.1) Describing a matrix that has mostly zero elements for structural reasons.
spectral convergence (§ 9.3) Exponentially rapid decrease in error as the number of interpolation nodes increases, e.g., as observed in Chebyshev polynomial and trigonometric interpolation.
stability region (§ 11.3) Region of the complex plane describing when numerical solution of a linear IVP is bounded as \(t\to\infty\).
step size (§ 6.2) Increment in time between successive solution values in a numerical IVP solver.
stiff (§ 6.7, § 11.4) Describes an IVP in which stability is a greater restriction than accuracy for many solution methods, usually favoring the use of an implicit time stepping method.
subtractive cancellation (§ 1.2) Growth in relative error that occurs when two numbers are added/subtracted to get a result that is much smaller in magnitude than the operands; also called loss of significance or cancellation error.
superlinear convergence (§ 4.4) Sequence for which the convergence is asymptotically faster than any linear rate.
symmetric matrix (§ 2.2) Square matrix that is equal to its transpose.
symmetric positive definite (SPD) matrix (§ 2.9) Matrix that is symmetric and positive definite, thereby permitting a Cholesky factorization. Correspondingly called hermitian positive definite in the complex case.
tensor-product domain (§ 13.1) A domain that can be parameterized using variables that lay in a logical rectangle or cuboid; i.e., each variable independently varies in an interval.
thin QR factorization (§ 3.3) Variant of the QR factorization that discards information not needed to fully represent the original matrix.
thin SVD (§ 7.3) Variant of the singular value decomposition that discards information not needed to fully represent the original matrix.
trapezoid formula (§ 5.6, § 6.6) Numerical integration method resulting from integration of a piecewise linear interpolant.
triangular matrix (§ 2.3) Matrix that is all zero either above (for lower triangular) or below (for upper triangular) the main diagonal.
tridiagonal matrix (§ 2.9) Matrix with nonzeros only on the main diagonal and the adjacent two diagonals.
trigonometric interpolation (§ 9.5) Interpolation of a periodic function by a linear combination of real or complex trigonometric functions.
truncation error (§ 5.5, § 5.6) Difference between an exact value and an approximation, such as one that truncates an infinite series.
unit triangular matrix (§ 2.4) Triangular matrix that has a 1 in every position on the main diagonal.
unit vector (§ 2.7) A vector whose norm equals 1.
unitary (§ 7.2) Square matrix with complex-valued entries whose columns are orthonormal.
unstable (§ 1.4) Allowing perturbations of the data to have much larger effects on the results than can be explained by the problem’s condition number.
upper Hessenberg (§ 8.4) Describing a matrix that has nonzeros only in the upper triangle and first subdiagonal.
Vandermonde matrix (§ 2.1) Matrix whose columns are formed from elementwise powers of a given vector, important for polynomial interpolation and approximation of data.
weights (§ 5.4, § 5.6, § 9.6) Coefficients in a linear combination of function values in a finite-difference or integration method.
zero-stable (§ 6.8) Boundedness property of multistep methods that is required for convergence.