Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Ordering — the series

9 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. natural1739reverse Cuthill–McKee1354minimum degree1026nested dissection1413matrix: 408 entries · dense factor: 10440bandwidth 12 · 4.26× the matrixbandwidth 12 · 3.32× the matrixbandwidth 123 · 2.51× the matrixbandwidth 108 · 3.46× the matrixn = 144, five-point stencilevery ordering fills in; none avoids it

    The order decides the memory

    Four elimination orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries. All four factorisations are exact, all four return the same answer, and the one with the better asymptotics is not the one that wins.

    part 1 · sparsity
  2. least possible76minimum degree76worst of 300 tie-breaks81reverse Cuthill–McKee85natural order9920 unknownstie-breaks at the least0.44minimum degree ÷ least1every order searched, by the set already eliminatedthe greedy rule found the minimum

    The least fill there is

    Finding the elimination order with the least fill is NP-hard, and that is a statement about the hardest graph and the largest size. On a graph of twenty vertices every one of the 20! orders can be searched at once, through the million sets of vertices already eliminated, and the least fill is a number. On the 4×4, 4×5 and 3×7 grids minimum degree finds it exactly. On eighty random sparse graphs of eighteen vertices it finds it on 53 and misses by at most 7.6 per cent, and on every one of the eighty some breaking of its ties finds it.

    part 2 · sparsity
  3. 6101418222610³10⁴10⁵grid side karithmeticND, totalMD, totalMD, critical pathND, critical pathdashed: the time on unbounded processorsthe same time, bought with more work

    An ordering that buys processors, not time

    Nested dissection loses to minimum degree on fill and on total work at every grid either measurement could draw. Read along the elimination tree a parallel factorisation works on, it does not win back the time either: its critical path is within 28 per cent of minimum degree's at every size from 8 to 24 points a side, in both directions, and the tree heights and widest columns are nearly the same. What it wins is the ratio. Its total work over its critical path — the most a factorisation on unbounded processors can speed up by — grows from 2.7 to 4.5 while minimum degree's stays between 2.1 and 2.6.

    part 3 · sparsity
  4. all 2^16 subsets searchedboth minima, one order0.97minimum degree optimal0.82worst fill overshoot1.1worst work overshoot1.111.021.041.0611.041.081.121.16fill ÷ the least filloperations ÷ the leastovershoot squaredon the diagonal: the two overshoots are equalon the upper curve: the arithmetic overshoot is the square

    Two minima that are one minimum

    The order that decides the memory found the operation count behaving like the square of the fill, which leaves room for an order with slightly more fill but a shorter heaviest column to do less arithmetic. Searched exactly over every elimination order on forty graphs, that order does not exist: one order attains both minima on thirty-nine of forty, and on the fortieth the least-fill order's arithmetic is 1.0099 times the least. Minimum degree attains both on the same thirty-three graphs and neither on the same seven.

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

    part 5 · sparsity
  6. 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.

    part 6 · sparsity
  7. 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.

    part 7 · sparsity
  8. 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.

    part 8 · sparsity
  9. 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.

    part 9 · sparsity

All series