# Glossary

**adjacency matrix** ({numref}`§ {number} <section-matrixanaly-insight>`)</br>
  Matrix whose nonzero entries show the links between nodes in a graph.

**adjoint** ({numref}`§ {number} <section-linsys-matrices>`)</br>
  Conjugate transpose of a complex matrix.

**advection equation** ({numref}`§ {number} <section-advection-traffic>`)</br>
  Archetypical PDE of hyperbolic type, representing transport phenomena.

**algorithm** ({numref}`§ {number} <section-intro-algorithms>`)</br>
  List of instructions for transforming data into a result.

**Arnoldi iteration** ({numref}`§ {number} <section-krylov-subspace>`)</br>
  Stable algorithm for finding orthonormal bases of nested Krylov subspaces.

**asymptotic** ({numref}`§ {number} <section-linsys-efficiency>`)</br>
  Relationship indicating that two functions have the same leading behavior in some limit.

**backward error** ({numref}`§ {number} <section-intro-stability>`)</br>
  Change to the input of a problem required to produce the result found by an inexact algorithm.

**backward substitution** ({numref}`§ {number} <section-linsys-linear-systems>`)</br>
  Systematic method for solving a linear system with an upper triangular matrix.

**bandwidth** ({numref}`§ {number} <section-linsys-structure>`)</br>
  The number of diagonals around the main diagonal that have nonzero elements.

**barycentric formula** ({numref}`§ {number} <section-globalapprox-barycentric>`)</br>
  Computationally useful expression for the interpolating polynomial as a ratio of rational terms.

**big-O** ({numref}`§ {number} <section-linsys-efficiency>`)</br>
  Relationship indicating that one function is bounded above by a multiple of another in some limit.

**boundary-value problem** ({numref}`§ {number} <section-bvp-tpbvp>`)</br>
  A differential equation with which partial information about the solution is given at multiple points on the boundary of the domain.

**cardinal function** ({numref}`§ {number} <section-localapprox-interpolation>`)</br>
  Interpolating function that is 1 at one node and 0 at all the others.

**Cholesky factorization** ({numref}`§ {number} <section-linsys-structure>`)</br>
  Symmetrized version of LU factorization for SPD matrices.

**collocation** ({numref}`§ {number} <section-bvp-linear>`)</br>
  Solution of a differential equation by imposing it approximately at a set of nodes.

**condition number** ({numref}`§ {number} <section-intro-conditioning>`)</br>
  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** ({numref}`§ {number} <section-localapprox-splines>`)</br>
  Piecewise cubic function with two globally continuous derivatives, most often used for interpolation or approximation.

**diagonalizable** ({numref}`§ {number} <section-matrixanaly-evd>`)</br>
  Matrix that admits an eigenvalue decomposition. Also known as nondefective.

**differentiation matrix** ({numref}`§ {number} <section-bvp-diffmats>`)</br>
  Matrix mapping a vector of function values to a vector of approximate derivative values.

**Dirichlet condition** ({numref}`§ {number} <section-bvp-tpbvp>`)</br>
  Boundary condition specifying the value of the solution.

**dominant eigenvalue** ({numref}`§ {number} <section-krylov-power>`)</br>
  Eigenvalue with the largest modulus (absolute value, in the real case).

**double precision** ({numref}`§ {number} <section-intro-floating-point>`)</br>
  Typical standard in floating-point representation, using 64 bits to achieve about 16 decimal significant digits of precision.

**eigenvalue** ({numref}`§ {number} <section-matrixanaly-evd>`)</br>
  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)** ({numref}`§ {number} <section-matrixanaly-evd>`)</br>
  Expression of a square matrix as the product of eigenvector and diagonal eigenvalue matrices.

**eigenvector** ({numref}`§ {number} <section-matrixanaly-evd>`)</br>
  Vector for which the action of a matrix is effectively one-dimensional. 

**Euler's method** ({numref}`§ {number} <section-ivp-euler>`)</br>
  Prototype of all IVP solution methods, obtained by assuming constant derivatives for the solution over short time intervals.

**evolutionary PDE** ({numref}`§ {number} <section-diffusion-blackscholes>`)</br>
  A partial differential equation in which one of the independent variables is time or a close analog.

**extrapolation** ({numref}`§ {number} <section-localapprox-integration>`)</br>
  Use of multiple discretization values to cancel out leading terms in an error expansion.

**finite difference** ({numref}`§ {number} <section-localapprox-finitediffs>`)</br>
  Linear combination of function values that approximates the value of a derivative of the function at a point.

**finite element method (FEM)** ({numref}`§ {number} <section-bvp-galerkin>`)</br>
  Use of piecewise integration to pose a linear system of equations for the approximate solution of a boundary-value problem.

**fixed point iteration** ({numref}`§ {number} <section-nonlineqn-fixed-point>`)</br>
  Repeated application of a function in hopes of converging to a fixed point.

**fixed point problem** ({numref}`§ {number} <section-nonlineqn-fixed-point>`)</br>
  Finding a value of a given function where the input and output values are the same; equivalent to rootfinding.

**floating-point numbers** ({numref}`§ {number} <section-intro-floating-point>`)</br>
  A finite set that substitutes for the real numbers in machine calculations. Denoted by $\mathbb{F}$.

**flops** ({numref}`§ {number} <section-linsys-efficiency>`)</br>
  Arithmetic operations on floating-point numbers, often counted as a proxy for computer runtime.

**forward substitution** ({numref}`§ {number} <section-linsys-linear-systems>`)</br>
  Systematic method for solving a linear system with a lower triangular matrix.

**Frobenius norm** ({numref}`§ {number} <section-linsys-norms>`)</br>
  Matrix norm computed by applying the vector 2-norm to a vector interpretation of the matrix.

**Gauss–Newton method** ({numref}`§ {number} <section-nonlineqn-nlsq>`)</br>
  Generalization of Newton's method for nonlinear least squares.

**Gaussian elimination** ({numref}`§ {number} <section-linsys-lu>`)</br>
  Use of row operations to transform a linear system to an equivalent one in triangular form.

**generating polynomials** ({numref}`§ {number} <section-ivp-multistep>`)</br>
  A pair of polynomials whose coefficients match those of a multistep method for IVPs.

**global error** ({numref}`§ {number} <section-ivp-euler>`)</br>
  Error made by an IVP method over the entire time interval of the solution.

**GMRES** ({numref}`§ {number} <section-krylov-gmres>`)</br>
  Iterative solution of a linear system through stable least-squares solutions on nested Krylov subspaces.

**graph** ({numref}`§ {number} <section-matrixanaly-insight>`)</br>
  Representation of a network as a set of nodes and edges.

**hat functions** ({numref}`§ {number} <section-localapprox-pwlin>`)</br>
  Cardinal functions for piecewise linear interpolation.

**heat equation** ({numref}`§ {number} <section-diffusion-blackscholes>`)</br>
  Archetypical parabolic PDE that describes diffusion.

**hermitian** ({numref}`§ {number} <section-matrixanaly-symm-eig>`)</br>
  Combination of transpose and elementwise complex conjugation. Also describes a matrix that equals its own hermitian.

**hermitian positive definite (HPD)** ({numref}`§ {number} <section-matrixanaly-symm-eig>`)</br>
  Matrix that is hermitian with strictly positive eigenvalues; complex variant of symmetric positive definite.

**identity matrix** ({numref}`§ {number} <section-linsys-matrices>`)</br>
  Matrix with ones on the diagonal and zeros elsewhere, acting as the multiplicative identity.

**ill-conditioned** ({numref}`§ {number} <section-intro-conditioning>`)</br>
  Exhibiting a large condition number, indicating high sensitivity of a result to changes in the data.

**implicit** ({numref}`§ {number} <section-ivp-multistep>`)</br>
  Formula that defines a quantity only indirectly, e.g., as the solution of a nonlinear equation.

**induced matrix norm** ({numref}`§ {number} <section-linsys-norms>`)</br>
  Norm computed using the interpretation of a matrix as a linear operator.

**initial-value problem (IVP)** ({numref}`§ {number} <section-ivp-basics>`, {numref}`§ {number} <section-ivp-systems>`)</br>
  An ordinary differential equation (possibly vector-valued) together with an initial condition.

**inner product** ({numref}`§ {number} <section-globalapprox-orthogonal>`)</br>
  Scalar or dot product of a pair of vectors, or its extension to a pair of functions.

**interpolation** ({numref}`§ {number} <section-linsys-polyinterp>`, {numref}`§ {number} <section-localapprox-interpolation>`)</br>
  Construction of a function that passes through a given set of data points.

**inverse iteration** ({numref}`§ {number} <section-krylov-inviter>`)</br>
  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** ({numref}`§ {number} <section-nonlineqn-newtonsys>`)</br>
  Matrix of first partial derivatives that defines the linearization of a vector-valued function.

**Kronecker product** ({numref}`§ {number} <section-twodim-laplace>`)</br>
  Alternative type of matrix multiplication useful for problems on a tensor-product domain.

**Krylov subspace** ({numref}`§ {number} <section-krylov-subspace>`)</br>
  Vector space generated by powers of a square matrix that is often useful for reducing the dimension of large problems.

**Lagrange formula** ({numref}`§ {number} <section-globalapprox-polynomial>`)</br>
  Theoretically useful expression for an interpolating polynomial.

**Lanczos iteration** ({numref}`§ {number} <section-krylov-minrescg>`)</br>
  Specialization of the Arnoldi iteration to the case of a hermitian (or real symmetric) matrix.

**Laplace equation** ({numref}`§ {number} <section-twodim-laplace>`)</br>
  Archetypical elliptic PDE describing a steady state.

**linear convergence** ({numref}`§ {number} <section-nonlineqn-fixed-point>`)</br>
  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** ({numref}`§ {number} <section-leastsq-fitting>`)</br>
  Minimization of the 2-norm of the residual for an overdetermined linear system.

**local truncation error** ({numref}`§ {number} <section-ivp-euler>`, {numref}`§ {number} <section-ivp-multistep>`)</br>
  Discretization error made in one time step of an IVP solution method.

**LU factorization** ({numref}`§ {number} <section-linsys-lu>`)</br>
  Factorization of a square matrix into the product of a unit lower triangular matrix and an upper triangular matrix.

**machine epsilon** ({numref}`§ {number} <section-intro-floating-point>`)</br>
  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** ({numref}`§ {number} <section-linsys-condition-number>`)</br>
  Norm of the matrix times the norm of its inverse, equivalent to the condition number for solving a linear system.

**method of lines** ({numref}`§ {number} <section-diffusion-methodlines>`)</br>
  Solution technique for partial differential equations in which each independent variable is discretized separately.

**multistep** ({numref}`§ {number} <section-ivp-multistep>`)</br>
  Formula using information over more than a single time step to advance the solution.

**Neumann condition** ({numref}`§ {number} <section-bvp-tpbvp>`)</br>
  Boundary condition specifying the derivative of the solution.

**Newton's method** ({numref}`§ {number} <section-nonlineqn-newton>`)</br>
  Rootfinding iteration that uses the linearization of the given function in order to define the next root approximation.

**nodes** ({numref}`§ {number} <section-localapprox-interpolation>`)</br>
  Values of the independent variable where an interpolant's values are prescribed.

**nonlinear least-squares problem** ({numref}`§ {number} <section-nonlineqn-nlsq>`)</br>
  Minimization of the 2-norm of the residual of a function that depends nonlinearly on a vector.

**norm** ({numref}`§ {number} <section-linsys-norms>`)</br>
  Means of defining the magnitude of a vector or matrix.

**normal** ({numref}`§ {number} <section-matrixanaly-evd>`)</br>
  Matrix that has a unitary eigenvalue decomposition.

**normal equations** ({numref}`§ {number} <section-leastsq-normaleqns>`)</br>
  Square linear system equivalent to the linear least-squares problem.

**numerical integration** ({numref}`§ {number} <section-localapprox-integration>`)</br>
  Estimation of a definite integral by combining values of the integrand, rather than by finding an antiderivative.

**one-step IVP method** ({numref}`§ {number} <section-ivp-euler>`)</br>
  IVP solver that uses information from just one time level to advance to the next.

**ONC matrix** ({numref}`§ {number} <section-leastsq-qr>`)</br>
  Matrix whose columns are orthonormal vectors.

**order of accuracy** ({numref}`§ {number} <section-localapprox-fd-converge>`, {numref}`§ {number} <section-localapprox-integration>`, {numref}`§ {number} <section-ivp-euler>`, {numref}`§ {number} <section-ivp-multistep>`)</br>
  Leading power of the truncation error as a function of a discretization size parameter.

**orthogonal vectors** ({numref}`§ {number} <section-leastsq-qr>`)</br>
  Nonzero vectors that have an inner product of zero.

**orthogonal matrix** ({numref}`§ {number} <section-leastsq-qr>`)</br>
  Square ONC matrix, i.e., matrix whose transpose is its inverse.

**orthogonal polynomials** ({numref}`§ {number} <section-globalapprox-orthogonal>`)</br>
  Family of polynomials whose distinct members have an integral inner product equal to zero, as with Legendre and Chebyshev polynomials.

**orthonormal vectors** ({numref}`§ {number} <section-leastsq-qr>`)</br>
  Vectors that are both mutually orthogonal and all of unit 2-norm.

**outer product** ({numref}`§ {number} <section-linsys-lu>`)</br>
  Multiplication of two vectors resulting in a rank-1 matrix.

**overdetermined** ({numref}`§ {number} <section-leastsq-fitting>`)</br>
  Characterized by having more constraints than available degrees of freedom.

**piecewise linear** ({numref}`§ {number} <section-localapprox-pwlin>`)</br>
  Function that is linear between each consecutive pair of nodes, but whose slope may jump at the nodes.

**PLU factorization** ({numref}`§ {number} <section-linsys-pivoting>`)</br>
  LU factorization with row pivoting.

**power iteration** ({numref}`§ {number} <section-krylov-power>`)</br>
  Repeated application of a matrix to a vector, followed by normalization, resulting in convergence to an eigenvector for the dominant eigenvalue.

**preconditioning** ({numref}`§ {number} <section-krylov-precond>`)</br>
  Use of an approximate inverse to improve the convergence rate of Krylov iterations for a linear system.

**pseudoinverse** ({numref}`§ {number} <section-leastsq-normaleqns>`)</br>
  Rectangular matrix that maps data to solution in the linear least-squares problem, generalizing the matrix inverse.

**QR factorization** ({numref}`§ {number} <section-leastsq-qr>`)</br>
  Representation of a matrix as the product of an orthogonal and an upper triangular matrix.

**quadratic convergence** ({numref}`§ {number} <section-nonlineqn-newton>`)</br>
  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** ({numref}`§ {number} <section-nonlineqn-quasinewton>`)</br>
  Rootfinding methods that overcome the issues of Jacobian computation and lack of global convergence in Newton's method.

**quasimatrix** ({numref}`§ {number} <section-globalapprox-orthogonal>`)</br>
  Collection of functions (such as orthogonal polynomials) that have algebraic parallels to columns of a matrix.

**Rayleigh quotient** ({numref}`§ {number} <section-matrixanaly-symm-eig>`)</br>
  Function of vectors that equals an eigenvalue when given its eigenvector as input.

**reduced QR factorization**</br>
  See *thin QR*.

**reduced SVD**</br>
  See *thin SVD*.

**residual** ({numref}`§ {number} <section-linsys-condition-number>`, {numref}`§ {number} <section-nonlineqn-rootproblem>`)</br>
  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** ({numref}`§ {number} <section-krylov-gmres>`)</br>
  Technique used in GMRES to prevent the work per iteration and overall storage from growing uncontrollably.

**rootfinding problem** ({numref}`§ {number} <section-nonlineqn-rootproblem>`)</br>
  Finding the input value for a given function which makes that function zero.

**row pivoting** ({numref}`§ {number} <section-linsys-pivoting>`)</br>
  Reordering rows during LU factorization to ensure that the factorization exists and can be computed stably.

**Runge phenomenon** ({numref}`§ {number} <section-globalapprox-stability>`)</br>
  Manifestation of the instability of polynomial interpolation at equally spaced nodes as degree increases.

**Runge--Kutta** ({numref}`§ {number} <section-ivp-rk>`)</br>
  One-step method for IVPs that evaluates the derivative of the solution more than once to advance a single step.

**secant method** ({numref}`§ {number} <section-nonlineqn-secant>`)</br>
  Scalar quasi-Newton method that uses a secant line rather than a tangent line to define a root estimate.

**shooting** ({numref}`§ {number} <section-bvp-shooting>`)</br>
  Unstable technique for solving a boundary-value problem in which an initial value is sought for by a rootfinding algorithm.

**simple root** ({numref}`§ {number} <section-nonlineqn-rootproblem>`)</br>
  Root of a function at which the derivative of the function is nonzero.

**singular value decomposition (SVD)** ({numref}`§ {number} <section-matrixanaly-svd>`)</br>
  Expression of a matrix as a product of two orthogonal/unitary matrices and a nonnegative diagonal matrix.

**sparse** ({numref}`§ {number} <section-linsys-structure>`, {numref}`§ {number} <section-krylov-structure>`)</br>
  Describing a matrix that has mostly zero elements for structural reasons.

**spectral convergence** ({numref}`§ {number} <section-globalapprox-stability>`)</br>
  Exponentially rapid decrease in error as the number of interpolation nodes increases, e.g., as observed in Chebyshev polynomial and trigonometric interpolation.

**stability region** ({numref}`§ {number} <section-diffusion-absstab>`)</br>
  Region of the complex plane describing when numerical solution of a linear IVP is bounded as $t\to\infty$.

**step size** ({numref}`§ {number} <section-ivp-euler>`)</br>
  Increment in time between successive solution values in a numerical IVP solver.

**stiff** ({numref}`§ {number} <section-ivp-implicit>`, {numref}`§ {number} <section-diffusion-stiffness>`)</br>
  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** ({numref}`§ {number} <section-intro-conditioning>`)</br>
  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** ({numref}`§ {number} <section-nonlineqn-secant>`)</br>
  Sequence for which the convergence is asymptotically faster than any linear rate.

**symmetric matrix** ({numref}`§ {number} <section-linsys-matrices>`)</br>
  Square matrix that is equal to its transpose.

**symmetric positive definite (SPD) matrix** ({numref}`§ {number} <section-linsys-structure>`)</br>
  Matrix that is symmetric and positive definite, thereby permitting a Cholesky factorization. Correspondingly called hermitian positive definite in the complex case.

**tensor-product domain** ({numref}`§ {number} <section-twodim-tensorprod>`)</br>
  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** ({numref}`§ {number} <section-leastsq-qr>`)</br>
  Variant of the QR factorization that discards information not needed to fully represent the original matrix.

**thin SVD** ({numref}`§ {number} <section-matrixanaly-svd>`)</br>
  Variant of the singular value decomposition that discards information not needed to fully represent the original matrix.

**trapezoid formula** ({numref}`§ {number} <section-localapprox-integration>`, {numref}`§ {number} <section-ivp-multistep>`)</br>
  Numerical integration method resulting from integration of a piecewise linear interpolant.

**triangular matrix** ({numref}`§ {number} <section-linsys-linear-systems>`)</br>
  Matrix that is all zero either above (for lower triangular) or below (for upper triangular) the main diagonal.

**tridiagonal matrix** ({numref}`§ {number} <section-linsys-structure>`)</br>
  Matrix with nonzeros only on the main diagonal and the adjacent two diagonals.

**trigonometric interpolation** ({numref}`§ {number} <section-globalapprox-trig>`)</br>
  Interpolation of a periodic function by a linear combination of real or complex trigonometric functions.

**truncation error** ({numref}`§ {number} <section-localapprox-fd-converge>`, {numref}`§ {number} <section-localapprox-integration>`)</br>
  Difference between an exact value and an approximation, such as one that truncates an infinite series.

**unit triangular matrix** ({numref}`§ {number} <section-linsys-lu>`)</br>
  Triangular matrix that has a 1 in every position on the main diagonal.

**unit vector** ({numref}`§ {number} <section-linsys-norms>`)</br>
  A vector whose norm equals 1.

**unitary** ({numref}`§ {number} <section-matrixanaly-evd>`)</br>
  Square matrix with complex-valued entries whose columns are orthonormal.

**unstable** ({numref}`§ {number} <section-intro-stability>`)</br>
  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** ({numref}`§ {number} <section-krylov-subspace>`)</br>
  Describing a matrix that has nonzeros only in the upper triangle and first subdiagonal.

**Vandermonde matrix** ({numref}`§ {number} <section-linsys-polyinterp>`)</br>
  Matrix whose columns are formed from elementwise powers of a given vector, important for polynomial interpolation and approximation of data.

**weights** ({numref}`§ {number} <section-localapprox-finitediffs>`, {numref}`§ {number} <section-localapprox-integration>`, {numref}`§ {number} <section-globalapprox-integration>`)</br>
  Coefficients in a linear combination of function values in a finite-difference or integration method.

**zero-stable** ({numref}`§ {number} <section-ivp-zerostability>`)</br>
  Boundedness property of multistep methods that is required for convergence.