Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Reduced stability — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 10⁻¹110¹10²-45-35-25-15-551525s, the smallest of the three interpolation pointsrightmost pole of the reduced modelunstable above this linebalanced truncation, order 3exact, and unusablefull system's pole-3.5placements swept19unstable models4worst pole24their interpolation1.3·10⁻¹⁴balanced truncation-0.84the conditions all holdand the model cannot be run

    A model that cannot be run

    A stable system, reduced by matching its transfer function at three points exactly, comes back with a pole in the right half plane at four of nineteen placements — and matches at all three points to 1.3·10⁻¹⁴ while doing it. The construction did what it promised.

    part 1 · reduction
  2. 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.

    part 2 · reduction
  3. 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.

    part 3 · reduction
  4. 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.

    part 4 · reduction
  5. 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.

    part 5 · reduction

All series