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 5 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 critical pathdepth one, pieces alone5.4·10⁴depth one, separator counted4.1·10⁴minimum degree, whole grid4.1·10⁴01000020000300004000050000dissection depthcritical path, Σ c² along the heaviest chain12348minimum degreepieces ordered aloneseparator countedgrey line: full dissectionthe penalty was the blindness

Pieces ordered blind

One level of nested dissection followed by minimum degree lengthened the factorisation's critical path, and the blame moved from the separator to the halves: minimum degree's path through a 12 × 24 half was longer than through the whole 24 × 24 grid. A 12 × 24 grid on its own has a path of 12,913, a third of the square's. What made the half expensive is that it was ordered as if the separator were not there. Count the separator's vertices in every degree and number them last, and the depth-one path falls from 53,508 to 41,050 — minimum degree's own — while the pieces' own arithmetic does not change at all. At depth two the same ordering beats full dissection.

sparsity · Ordering longest ÷ shortesttwo rows, 12²1.5two rows, 24²1.311.11.21.31.41.5longest ÷ shortest critical path12²16²20²24²12²16²20²24²g1g2g312²16²20²24²grid, one rowgrid, level setgeometric graphgrid, two rowsdashed: every shuffle gives the same factorfree unless the separator is thick

A clique has no order

Ordering a dissection's pieces with their separator in view cut the critical path by a quarter, and the next proposal was to order the separator's own vertices by how much fill each carries in. On every separator the dissections here produce — the grid's rows, its level-set diagonals, and the level sets of three irregular graphs of 300 vertices — twenty-four shuffles of the separator's order give the same factor to the last entry. The reason is one line of graph theory: once the pieces are eliminated, a separator whose vertices all touch one connected piece is a clique, and a clique's order changes nothing. The order matters only on a separator that is not a clique, and the one built here to be that — two grid rows thick — loses to a separator of one row under every order tried. The separator's size is the decision; its order is not one.

sparsity · Ordering 0102030405060radius 0.11graph 1cliquegraph 2cliquegraph 3cliquegraph 4cliquegraph 5cliquegraph 6cliquegraph 7cliquegraph 8cliqueradius 0.13graph 1cliquegraph 2cliquegraph 3cliquegraph 4cliquegraph 5cliquegraph 6cliquegraph 7cliquegraph 8cliqueradius 0.16graph 1cliquegraph 2cliquegraph 3cliquegraph 4cliquegraph 5cliquegraph 6cliquegraph 7cliquegraph 8cliqueseparator vertices; dark: touching only one sideevery one a clique, at every densityspare vertices, no broken clique

The spare vertices lean one way

Every separator a dissection drew on grids and sparse geometric graphs was a clique once its pieces were eliminated, so the order inside it changed nothing; only a separator two rows thick, built by hand, was not. On geometric graphs at twice the density, level-set separators were predicted to come out several vertices thick where the level crosses a dense patch, with vertices touching only one side — failing the clique condition, making their order matter by more than five per cent, and paying more for trimming than for any order. On twenty-four graphs at three densities the spare vertices are there: up to thirteen in one separator. Not one separator fails the clique condition, because on every graph the spare vertices all touch the same piece, and two vertices that share a piece are joined through it. No shuffle of any separator moves the fill or the work by a single entry. Trimming the spare vertices into the piece they touch shortens the critical path by up to 48 per cent — and denser graphs have fewer of them, not more.

sparsity · Ordering

Named alongside it

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

Elimination treeFill-inFill-reducing orderingMinimum degreeNested dissectionSeparatorFlop countSymbolic factorisationSparsity

All concepts