Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Critical path — where it appears

The most expensive chain of dependent work in a computation, here the largest total of column work along a path of the elimination tree. It is what a factorisation takes on unbounded processors, and total work divided by it bounds the speedup any number of processors can buy.

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

total operationswork, no dissection10⁵work, full dissection1.5·10⁵work, one level1.3·10⁵on unbounded processorscritical path, no dissection4.1·10⁴least, at depth 43.4·10⁴critical path, one level5.4·10⁴10⁵switching depthoperations01234568total operationscritical pathdepth 0 is minimum degree, depth 8 is nested dissectiondepth 1 is worse than both

The depth that is worse than both ends

Nested dissection to a chosen depth and minimum degree below it is the ordering codes ship, and sweeping the depth was supposed to find a setting that keeps most of dissection's parallelism for most of minimum degree's work. It does not exist: total work rises with the depth at every grid size, and one depth — the first — is worse than both extremes on work and on the critical path at all four sizes measured. One bisection buys nothing because there is no recursion under it to amortise the separator.

sparsity · Ordering rows and columns, from the coordinateslevel structures, from the graph aloneseparator, level 1separator, level 2separator, level 3same vertex count in the first cutdifferent pieces under it

The halves were the price

One level of nested dissection followed by minimum degree was worse than both no dissection and full dissection on a grid, and the explanation offered was the separator's dense block sitting on every path. That predicted a sign: a separator found from the graph, rather than read off the coordinates, should make the penalty larger. It makes it smaller at every size — 44,116 against 53,508 at 24×24 — and the separator is not where the difference is: both first separators have 24 vertices and cost exactly 4,900. What differs is the path through the halves. Minimum degree takes 48,608 through a rectangular half of the 24×24 grid, longer than its 41,072 through the whole grid, and 39,216 through a triangular one.

sparsity · Ordering

Named alongside it

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

Elimination treeFill-inFill-reducing orderingFlop countMinimum degreeNested dissectionSeparatorSymbolic factorisationSparsity

All concepts