Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Discrete laplacian — where it appears

The matrix of the second-difference stencil on a regular grid, tridiagonal in one dimension and a Kronecker sum of copies of itself in more. Its whole spectrum is a formula in sines, which is why so much on this site is measured against it.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

03672108144180216024681012eigenvalues in orderλthe closed formmarks: the assembled matrix, decomposeda spectrum nobody computedrows of the matrix216numbers that describe it108λ smallest0.59λ largest11worst |computed − exact|7.1·10⁻¹³the matrix is never neededand neither is its decomposition

An index that is a pair

A discretisation on a two-dimensional grid of n points a side has n² unknowns and a matrix with n⁴ entries — 10⁸ at n = 100. What that matrix is instead is two Kronecker products of an n × n matrix, which is 2n² numbers, and nothing has been approximated: assembling it was the mistake.

tensor · kronecker 024681012141610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹index of the singular value at the cutσ ⁄ σ₁eight digits10^-4: 5 Kronecker terms10^-8: 7 Kronecker terms10^-12: 8 Kronecker termsnot closed, and nearly closedrank at the cut8a Kronecker product's1terms at 10⁻⁴5terms at 10⁻⁸7terms a decade0.5the inverse leaves the formatby half a term a decade

A solve that is d decompositions

A Kronecker sum is closed under nothing useful — its inverse is not a Kronecker sum and no factorisation of it is one. What it has instead is eigenvectors that are Kronecker products, so a solve with 1,728 unknowns takes one decomposition of a 12 × 12 matrix and nothing else.

tensor · kronecker

Named alongside it

The objects these essays reach for when they reach for this one.

Condition numberExact ground truthKronecker productKronecker sumModel problemSeparabilityCurse of dimensionalityFlop countMatrix-freeOff diagonal rankPreconditioningUnfolding

All concepts