Glossary - Fundamentals of Numerical Computation

absolute stability: Boundedness of the numerical solution of a linear IVP as $t\to\infty$ . (Definition 11.3.1)
adjacency matrix: Matrix whose nonzero entries show the links between nodes in a graph. (Definition 7.1.1)
adjoint: Conjugate transpose of a complex matrix. (Definition 2.2.1)
advection equation: Archetypical PDE of hyperbolic type, representing transport phenomena. (Definition 12.1.1)
algebraic convergence: Sequence in which the difference between sequence value and limit asymptotically decreases as an integer power of a step size or a number of nodes, appearing as a straight line on a log-log convergence plot. (Definition 5.2.2)
algorithm: List of instructions for transforming data into a result. (Algorithms)
Arnoldi iteration: Stable algorithm for finding orthonormal bases of nested Krylov subspaces. (Definition 8.4.2)
asymptotic: Relationship indicating that two functions have the same leading behavior in some limit. (Definition 2.5.1)
backward error: Change to the input of a problem required to produce the result found by an inexact algorithm. (Definition 1.4.1)
backward substitution: Systematic method for solving a linear system with an upper triangular matrix. (2.3.9)
bandwidth: The number of diagonals around the main diagonal that have nonzero elements. (Definition 2.9.2)
barycentric interpolation formula: Computationally useful expression for the interpolating polynomial as a ratio of rational terms. (9.2.3)
big-O: Relationship indicating that one function is bounded above by a multiple of another in some limit. (Definition 2.5.1)
boundary-value problem: A differential equation with which partial information about the solution is given at multiple points on the boundary of the domain. (Definition 10.1.1)
cardinal function: Interpolating function that is 1 at one node and 0 at all the others. (Definition 5.1.2)
Cholesky factorization: Symmetrized version of LU factorization for SPD matrices. (Theorem 2.9.3)
collocation: Solution of a differential equation by imposing it approximately at a set of nodes. (10.4.7)
condition number: Ratio of the size of change in the output of a function to the size of change in the input that produced it. (Definition 1.2.1)
cubic spline: Piecewise cubic function with two globally continuous derivatives, most often used for interpolation or approximation. (Definition 5.3.1)
diagonalizable matrix: Matrix that admits an eigenvalue decomposition. Also known as nondefective. (Definition 7.2.3)
differentiation matrix: Matrix mapping a vector of function values to a vector of approximate derivative values. (Definition 10.3.1)
Dirichlet condition: Boundary condition specifying the value of the solution. (Definition 10.1.2)
domain of dependence: Part of a PDE domain that can potentially influence the solution at a given point. (Definition 12.2.1, Definition 12.2.2)
dominant eigenvalue: Eigenvalue with the largest magnitude (absolute value, in the real case). (Definition 8.2.1)
double precision: Typical standard in floating-point representation, using 64 bits to achieve about 16 decimal significant digits of precision. (1.1.12)
eigenvalue: Scalar $\lambda$ such that $\mathbf{A}\mathbf{x} = \lambda \mathbf{x}$ for a square matrix $\mathbf{A}$ and nonzero vector $\mathbf{x}$ . (Definition 7.2.1)
eigenvalue decomposition: Expression of a square matrix as the product of eigenvector and diagonal eigenvalue matrices. Abbreviated EVD. (Definition 7.2.3)
eigenvector: Vector for which the action of a matrix is effectively one-dimensional. (Definition 7.2.1)
Euler’s method: Prototype of all IVP solution methods, obtained by assuming constant derivatives for the solution over short time intervals. (Definition 6.2.1)
evolutionary PDE: A partial differential equation in which one of the independent variables is time or a close analog. (Definition 11.1.1)
extrapolation: Use of multiple discretization values to cancel out leading terms in an error expansion. (Section 5.6.2)
finite-difference formula: Linear combination of function values that approximates the value of a derivative of the function at a point. (Definition 5.4.1)
finite element method (FEM): Use of piecewise integration to pose a linear system of equations for the approximate solution of a boundary-value problem. (Section 10.6.3)
fixed-point iteration: Repeated application of a function in hopes of converging to a fixed point. (Definition 4.2.2)
fixed-point problem: Finding a value of a given function where the input and output values are the same; equivalent to rootfinding. (Definition 4.2.1)
floating-point numbers: A finite set that substitutes for the real numbers in machine calculations. Denoted by $\mathbb{F}$ . (Definition 1.1.1)
flop: A single arithmetic operation on floating-point numbers, often counted as a proxy for computer runtime. (Definition 2.5.2)
forward substitution: Systematic method for solving a linear system with a lower triangular matrix. (2.3.7)
Frobenius norm: Matrix norm computed by applying the vector 2-norm to a vector interpretation of the matrix. (Definition 2.7.3)
Galerkin conditions: Integration conditions that can be used to define an approximate solution of a BVP. (10.6.10)
Gauss–Newton method: Generalization of Newton’s method for nonlinear least squares. (Definition 4.7.2)
Gaussian elimination: Use of row operations to transform a linear system to an equivalent one in triangular form. (Section 2.4.4)
generating polynomials: A pair of polynomials whose coefficients match those of a multistep method for IVPs. (Definition 6.6.2)
global error: Error made by an IVP method over the entire time interval of the solution. (Definition 6.2.4)
GMRES: Iterative solution of a linear system through stable least-squares solutions on nested Krylov subspaces. (Section 8.5.1)
graph: Representation of a network as a set of nodes and edges. (Definition 7.1.1)
hat functions: Cardinal functions for piecewise linear interpolation. (5.2.2)
heat equation: Archetypical parabolic PDE that describes diffusion. (Definition 11.1.2)
hermitian: Combination of transpose and elementwise complex conjugation. Same as the adjoint. (Definition 2.2.1)
hermitian matrix: A matrix that equals its own adjoint. Also known as self-adjoint. (Definition 2.2.2)
HPD matrix: Matrix that is hermitian with strictly positive eigenvalues; complex variant of SPD. (Definition 7.4.2)
homogeneous boundary condition: Having a zero value. (Definition 10.1.2)
identity matrix: Matrix with ones on the diagonal and zeros elsewhere, acting as the multiplicative identity. (Definition 2.2.3)
ill-conditioned: Exhibiting a large condition number, indicating high sensitivity of a result to changes in the data. (Section 1.2.2)
implicit: Formula that defines a quantity only indirectly, e.g., as the solution of a nonlinear equation. (Definition 6.6.1)
induced matrix norm: Norm computed using the interpretation of a matrix as a linear operator. (Definition 2.7.4)
initial-value problem: An ordinary differential equation (possibly vector-valued) together with an initial condition. Abbreviated IVP. (Definition 6.1.1, Definition 6.3.1)
inner product: Scalar or dot product of a pair of vectors, or its extension to a pair of functions. ((A.4), Definition 9.4.1)
interpolation: Construction of a function that passes through a given set of data points. (Definition 2.1.1, Definition 5.1.1)
inverse iteration: 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. (Definition 8.3.1)
Jacobian matrix: Matrix of first partial derivatives that defines the linearization of a vector-valued function. (Definition 4.5.2)
Kronecker product: Alternative type of matrix multiplication useful for problems on a tensor-product domain. (Definition 13.3.2)
Krylov subspace: Vector space generated by powers of a square matrix that is often useful for reducing the dimension of large problems. (Definition 8.4.1)
Lagrange formula: Theoretically useful expression for an interpolating polynomial. (Theorem 9.1.2)
Lanczos iteration: Specialization of the Arnoldi iteration to the case of a hermitian (or real symmetric) matrix. (8.6.2)
Laplace equation: Archetypical elliptic PDE describing a steady state. (Definition 13.3.1)
linear convergence: 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. (Definition 4.2.3)
linear least-squares problem: Minimization of the 2-norm of the residual for an overdetermined linear system. (Definition 3.1.1)
local truncation error: Discretization error made in one time step of an IVP solution method. (Definition 6.2.3, Definition 6.6.3)
LU factorization: Factorization of a square matrix into the product of a unit lower triangular matrix and an upper triangular matrix. (Definition 2.4.2)
machine epsilon: 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. (Definition 1.1.2)
matrix condition number: Norm of the matrix times the norm of its inverse, equivalent to the condition number for solving a linear system. (Definition 2.8.1)
method of lines: Solution technique for evolutionary partial differential equations in which each independent variable is discretized separately. Also called semidiscretization. (Section 11.2.1)
multistep: Formula using information over more than a single time step to advance the solution. (Definition 6.6.1)
Neumann condition: Boundary condition specifying the derivative of the solution. (Definition 10.1.2)
Newton’s method: Rootfinding iteration that uses the linearization of the given function in order to define the next root approximation. (Definition 4.3.1)
nodes: Values of the independent variable where an interpolant’s values are prescribed. (Definition 5.1.1)
nonlinear least-squares problem: Minimization of the 2-norm of the residual of a function that depends nonlinearly on a vector. (Definition 4.7.1)
norm: Means of defining the magnitude of a vector or matrix. (Definition 2.7.1, Definition 2.7.3, Definition 2.7.4)
normal matrix: Matrix that has a unitary matrix of eigenvectors in an eigenvalue decomposition. (Definition 7.2.5)
normal equations: Square linear system equivalent to the linear least-squares problem. (Definition 3.2.1)
numerical integration formula: Estimation of a definite integral by combining values of the integrand, rather than by finding an antiderivative. (Definition 5.6.1)
one-step IVP method: IVP solver that uses information from just one time level to advance to the next. (Definition 6.2.2)
ONC matrix: Matrix whose columns are orthonormal vectors. (This term is peculiar to this book.) (Definition 3.3.2)
order of accuracy: Leading power of the truncation error as a function of a discretization size parameter. (Definition 5.2.2, Definition 5.5.2, Definition 5.6.3, Definition 6.2.5, Definition 6.6.3)
orthogonal vectors: Nonzero vectors that have an inner product of zero. (Definition 3.3.1)
orthogonal matrix: Square ONC matrix, i.e., matrix whose transpose is its inverse. (Definition 3.3.3)
orthogonal polynomials: Family of polynomials whose distinct members have an integral inner product equal to zero, as with Legendre and Chebyshev polynomials. (Definition 9.4.4, Definition 9.4.5)
orthonormal vectors: Vectors that are both mutually orthogonal and all of unit 2-norm. (Definition 3.3.1)
outer product: Multiplication of two vectors resulting in a rank-1 matrix. (A.5)
overdetermined: Characterized by having more constraints than available degrees of freedom. (Definition 3.1.1)
piecewise linear: Function that is linear between each consecutive pair of nodes, but whose slope may jump at the nodes. (Definition 5.2.1)
PLU factorization: LU factorization with row pivoting. (Definition 2.6.2)
Poisson equation: Generalization of Laplace equation with a nonzero forcing function. (Definition 13.3.1)
power iteration: Repeated application of a matrix to a vector, followed by normalization, resulting in convergence to an eigenvector for the dominant eigenvalue. (Definition 8.2.2)
preconditioner: An approximate matrix or its inverse, used to improve the convergence rate of Krylov iterations for a linear system. (Definition 8.8.1)
pseudoinverse: Rectangular matrix that maps data to solution in the linear least-squares problem, generalizing the matrix inverse. (Definition 3.2.2)
QR factorization: Representation of a matrix as the product of an orthogonal and an upper triangular matrix. (Theorem 3.3.3, Definition 3.3.4)
quadratic convergence: Sequence in which the difference between sequence value and limit asymptotically decreases by a constant times the square of the preceding difference. (Definition 4.3.2)
quasi-Newton methods: Rootfinding methods that overcome the issues of Jacobian computation and lack of global convergence in Newton’s method. (Quasi-Newton methods)
quasimatrix: Collection of functions (such as orthogonal polynomials) that have algebraic parallels to columns of a matrix. (Definition 9.4.2)
Rayleigh quotient: Function of vectors that equals an eigenvalue when given its eigenvector as input. (Definition 7.4.1)
reduced QR factorization: See thin QR.
reduced SVD: See thin SVD.
residual: 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. (Definition 2.8.2, Definition 4.1.2)
restarting: Technique used in GMRES to prevent the work per iteration and overall storage from growing uncontrollably. (Section 8.5.3)
rootfinding problem: Finding the input value for a given function which makes that function zero. (Definition 4.1.1, Definition 4.5.1)
row pivoting: Reordering rows during LU factorization to ensure that the factorization exists and can be computed stably. (Definition 2.6.1)
Runge phenomenon: Manifestation of the instability of polynomial interpolation at equally spaced nodes as degree increases. (Section 9.3.1)
Runge–Kutta: One-step method for IVPs that evaluates the derivative of the solution more than once to advance a single step. (6.4.10)
secant method: Scalar quasi-Newton method that uses a secant line rather than a tangent line to define a root estimate. (Definition 4.4.1)
shooting: Unstable technique for solving a boundary-value problem in which an initial value is sought for by a rootfinding algorithm. (10.2.2)
similar matrices: Matrices that are linked by a similarity transformation, thus sharing the same set of eigenvalues. (Definition 7.2.4)
similarity transformation: Mapping $\mathbf{A} \mapsto \mathbf{S}\mathbf{A}\mathbf{S}^{-1}$ for an invertible $\mathbf{S}$ . The transformation leaves eigenvalues, but not eigenvectors, unchanged. (Definition 7.2.4)
simple root: Root of a function at which the derivative of the function is nonzero; i.e., a root of multiplicity 1. (Definition 4.1.3)
singular value decomposition: Expression of a matrix as a product of two orthogonal/unitary matrices and a nonnegative diagonal matrix. (Abbreviated SVD.) (Definition 7.3.1)
sparse matrix: Describing a matrix that has mostly zero elements for structural reasons. (Section 2.9.1, Sparsity and structure)
SPD matrix: Matrix that is symmetric and positive definite, thereby permitting a Cholesky factorization. Correspondingly called HPD in the complex case. (Definition 2.9.3)
spectral convergence: Exponentially rapid decrease in error as the number of interpolation nodes increases, e.g., as observed in Chebyshev polynomial and trigonometric interpolation. (Theorem 9.3.1)
stability region: Region of the complex plane describing when numerical solution of a linear IVP has absolute stability. (Definition 11.3.2)
step size: Increment in time between successive solution values in a numerical IVP solver. (6.2.2)
stiff differential equation: 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. (Example 6.7.2, Stiffness)
subtractive cancellation: 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. (1.2.7)
superlinear convergence: Sequence for which the convergence is asymptotically faster than any linear rate. (Definition 4.4.2)
symmetric matrix: Square matrix that is equal to its transpose. (Definition 2.2.2)
tensor-product domain: 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. (Definition 13.1.1)
thin QR: Variant of the QR factorization that discards information not needed to fully represent the original matrix. (Definition 3.3.4)
thin SVD: Variant of the singular value decomposition that discards information not needed to fully represent the original matrix. (7.3.10)
trapezoid formula: Numerical integration method resulting from integration of a piecewise linear interpolant. (Definition 5.6.2, Table 6.6.1)
triangular matrix: Matrix that is all zero either above (for lower triangular) or below (for upper triangular) the main diagonal. (Section 2.3.2, Definition A.1)
tridiagonal matrix: Matrix with nonzeros only on the main diagonal and the adjacent two diagonals. (Definition 2.9.2)
trigonometric polynomial: Linear combination of real or complex trigonometric functions at multiples of a base frequency. (Definition 9.5.1)
truncation error: Difference between an exact value and an approximation, such as one that truncates an infinite series. (Definition 5.5.1, Definition 5.6.3, Definition 6.2.3)
unit triangular matrix: Triangular matrix that has a 1 in every position on the main diagonal. (Definition 2.4.1)
unit vector: A vector whose norm equals 1. (Definition 2.7.2)
unitary matrix: Square matrix with complex-valued entries whose columns are orthonormal. (Definition 7.2.2)
unstable: Allowing perturbations of the data to have much larger effects on the results than can be explained by the problem’s condition number. (Stability)
upper Hessenberg matrix: Matrix that has nonzeros only in the upper triangle and first subdiagonal. (Definition 8.4.3)
upwind: Direction opposite to the flow of information in an evolutionary PDE. (Definition 12.2.3)
Vandermonde matrix: Matrix whose columns are formed from elementwise powers of a given vector, important for polynomial interpolation and approximation of data. (Definition 2.1.2)
wave equation: Evolutionary PDE that allows propagation in all directions equally. (12.4.1)
weights: Coefficients applied within a linear combination of function values in a finite-difference or integration method. (Definition 5.4.1, Definition 5.6.1, Definition 9.2.1)
zero-stable: Describing a multistep method having a boundedness property that is required for convergence. (Definition 6.8.1)