Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Galerkin projection — where it appears

Reducing a matrix or a model by restricting it to a subspace and testing against the same subspace, so the reduced matrix is VᵀAV for an orthonormal basis V. It keeps whatever the numerical range guarantees and gives up the extra conditions a second subspace would buy.

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

Also named here as numerical range — the same set of essays touches all of them, so they are one junction rather than several.

10⁻¹110¹10²s, the smallest interpolation pointrightmost pole of the reduced model−10−10+1+10unstable above zeronumerical range edge, -0.986system's abscissa, -3.49two-sided, order 3one-sided, order 3one-sided, order 6Pe 10, nineteen placementssystem's rightmost eigenvalue-3.5edge of the numerical range-0.99two-sided, order 3: unstable placements4one-sided, order 3: unstable placements0one-sided, order 6: unstable placements0signed logarithmic axisshaded: poles in the right half plane

Half the conditions and a certificate

A two-sided interpolatory reduction of a stable convection–diffusion system came back unstable at four placements of nineteen. The one-sided reduction built from the same kind of solves came back stable at all 152 placements measured across eight Péclet numbers, and not by luck: every pole of a Galerkin model lies inside the numerical range of the operator, whose edge here is exactly the diffusion term's largest eigenvalue, −0.986 at Péclet 10. The price is the slope conditions, and spent as six one-sided shifts instead of three two-sided ones it beats the stable two-sided model at seven placements of ten.

reduction · Reduced stability edge of the numerical rangespectrum, -3.49zero37.9-0.986-3.496.59unstable one-sided models, of nineteen placements051015-3-2-1.5-1-0.500.511.522.53cond 1.4·10⁶cond 112t, the rescaling exponent — the k-th state is multiplied by γ to the power tk; t = 1 symmetrisesorder 1order 2order 3order 6the transfer function is the same at every tonly the inner product changes

A certificate written in coordinates

Every one-sided reduced model of the convection–diffusion system was stable, because its poles cannot leave the numerical range and the range sat in the left half plane. Rescale the state by a diagonal matrix and nothing about the system changes — not its eigenvalues, not its transfer function, not one pole of any two-sided model — but the numerical range moves. At Péclet 40 a rescaling with condition number 260 pushes its edge to +6.6 and ten placements of nineteen return unstable one-sided models. Projecting in the inner product of a Lyapunov solution puts the certificate back in any coordinates.

reduction · Reduced stability Péclet 100, orders 1, 2, 3, 6nodal edge at 1,000, outflow8.9weighted edge at 1,000-0.097unstable nodal models7110¹10²10³-20246810largest cell over smallestright edge of the numerical rangenodal, small cells at the outflownodal, small cells at the inflowcell-size weightedabove the dashed line the certificate is goneit is a sufficient condition, not a failure

The inner product the mesh already computed

A Galerkin reduced model is certified stable when the operator's numerical range sits in the left half plane, and the certificate belongs to the coordinates. The coordinates that broke it before were a constructed rescaling. Grade a convection–diffusion mesh towards its outflow boundary layer — the grading anyone resolving the layer would choose — and nodal values break it too: the range's edge is past zero at a ratio of ten and reaches +8.9 at a thousand, and at Péclet 100 seven reduced models come back unstable. Weight the projection by the cell sizes the discretisation already computed and every model at every grading is stable, with the range's edge back at −0.098.

reduction · Reduced stability Péclet 100centred nodal edge at 1,0008.9upwind nodal edge at 1,0006.8upwind weighted edge at 1,000-0.45110¹10²10³-202468largest cell over smallestright edge of the numerical rangecentred, nodalupwind, nodalcentred, weightedupwind, weightedabove the dashed line the certificate is goneupwinding lowers the line and does not cross it

The smaller cell downstream

Nodal values on a convection–diffusion mesh graded towards its outflow layer put the numerical range in the right half plane, and Galerkin reduced models then fail. A code that grades towards the layer usually also upwinds, and upwinding adds diffusion. It does not give the certificate back: at Péclet 100 and a grading of a thousand the range's edge falls from 8.94 to 6.78 and stays positive, and 18 reduced models fail where 23 did. Each row of the upwind stencil's symmetric part sums to half the difference between the inverse widths of the cell after the node and the cell before it, so wherever the cells shrink downstream the dissipation upwinding adds is outweighed by the coupling to the smaller cell next door.

reduction · Reduced stability Péclet 100, ratio 1000centred edge8.9upwind edge6.8cell Péclet at upwind peak0.5800.20.40.60.81node position xweight of the edge eigenvectorcell Péclet onecentredupwindthirty interior nodes; the outflow layer is at x = 1where diffusion and convection meet

The edge sits where the cells meet the flow

On a convection–diffusion mesh graded towards its outflow, the nodal numerical range reaches into the right half plane, and Galerkin reduced models fail. The account was that the edge lives in the cells where diffusion and convection are comparable, and drawing the eigenvector that attains it says the account is right: on every operator whose mesh has a cell Péclet number above one, the eigenvector peaks where that number is between a half and one and a quarter, just downstream of where it crosses one, and the outflow layer's five smallest cells hold under four per cent of it. The other question has a short answer too. A one-sided stencil scaled by a cell width is dissipative in nodal coordinates only if its weights do not grow downstream, and a consistent one must grow there: the only dissipative weight is the constant one, which is wrong by up to four units of the derivative.

reduction · Reduced stability Péclet 100nodal edge, ratio 10008.9band-only edge, ratio 1000144cell sizes everywhere-0.097110¹10²10³largest cell over smallestrange edge−0.20110100nodalcell sizes everywherecell sizes in the bandcell sizes outside the banddashed: zero, the certificate's linea weight is not a location

A weight is not a location

On a mesh graded towards a convection–diffusion operator's outflow, the edge of the numerical range in nodal coordinates lives in the cells where diffusion and convection are comparable, and weighting the inner product by cell size everywhere moves it into the left half plane. The prediction was that the weight is only needed where the edge lives: cell sizes over the nodes whose cell Péclet number is between a quarter and two, and one elsewhere, would make the range dissipative at every grading and repair every failed model. It does the opposite. From a grading of ten the band-only weight's edge is positive, and from thirty it is further right than the nodal edge it was meant to repair — 144 against 8.9 at Péclet 100. Its edge eigenvector leaves the transition and sits at the weight's own step, where it rises from 0.16 to 1; and its models fail on thirteen placements to the nodal twenty-three. The cell sizes work because they are the one diagonal weight that makes the centred convection stencil skew, row by row, and any other — stepped, ramped over half the mesh, or the reverse — leaves a symmetric part where it departs.

reduction · Reduced stability

Named alongside it

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

Convection diffusionNon-normalityNumerical rangeReduced stabilityMass matrixTransfer functionPetrov–GalerkinRational krylovLyapunov equationPeclet numberUpwindingBalanced truncation

All concepts