Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Synchronisation — where it appears

A point at which every processor must agree on a value before any can continue, which an iteration of a Krylov method needs at least one of.

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

10²11.251.51.7522.25processorstraffic saved, as a factorthe √4 the law promisesbreak-evenmeasureda limit is not a sizesaving at p = 640.88saving at p = 5761.4what the law promises2memory, as a factor4a loss at sixty-four processorsand 72% of the law at five hundred

Memory bought with messages

Holding four copies of the data instead of one is supposed to cut a matrix multiplication's communication by √4. Measured on a machine of 64 processors it costs 14% more traffic; at 576 it saves 44%, which is 72% of what the law promises. The memory is exactly four times, and that part is not asymptotic.

cost · communication an eigenvalue repeated 2 times, in a 200-dimensional problemblock of 1never returns them allblock of 232 products, 16 stepsblock of 351 products, 17 stepsblock of 460 products, 15 stepsblock of 570 products, 14 stepsblock of 684 products, 14 stepsthe narrowest that workscheapest width2its products with A32the widest drawn84narrower than the multiplicity is not slowit is absent

How wide the block should be

A block narrower than the multiplicity does not converge slowly — it never returns the missing copy at all. Above the multiplicity every extra column buys iterations at about ten products with A each. And the mechanism that is supposed to make the choice unimportant never fires from a random start.

spectra · invariant subspace

Named alongside it

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

All reduceAsymptotic analysisBlock methodsBlock transferBroadcastCommunicationCommunication avoidingDeflationInvariant subspaceKrylov subspaceLanczosLatency

All concepts