On the bit-complexity of discrete solutions of PDEs: Compact multigrid

The topic of Partial Differential Equations (PDEs) is an interesting area where the techniques of discrete mathematics and numerical algorithms can be brought together to solve problems that would normally be considered more properly in the domain of continuous mathematics. We investigate the bit-complexity of discrete solutions to linear PDEs, which is a realistic measure for parallel computers such as the CONNECTION MACHINE (CM1) and MASPAR. We show that for a large class of linear PDEs satisfying some routine assumptions of the multigrid methods, the N point discretization of their solution can be compressed to only a constant number of bits per discretization point, without loss of information or introducing errors beyond the order of the discretization error. More specifically, we show that the bit-complexity of the compressed solution is O(N) for both storage space and the total number of operations. We also compute the compressed solution by a parallel algorithm using O(logN) time and N/logN bit-serial processors. The best previous bounds on the bit-complexity (for both sequential time and storage space) were at least NlogN; furthermore, the order of NlogN bit-serial processors were required to support the O(logN) parallel time in the known algorithms. We believe this is the first case where a linear or algebraic system can be provably compressed (i.e. the bit-complexity of storage of the compressed solution is less than the solution size) and also the first case where the use of data compression provably speeds up the time to solve the system (in the compressed form).