Compact Multigrid
Victor Ya. Pan, John H. Reif · SIAM Journal on Scientific and Statistical Computing · 1992
The bit-complexity is a realistic complexity measure for computations on parallel computers such as the CONNECTION MACHINE (CM1) and the MASPAR. For a large class of linear PDEs satisfying some routine assumptions of the multigrid methods, the N point discretization of their solution is compressed to a constant number of bits per discretization point with no loss of information and without introducing errors beyond the order of the discretization error. Namely, it is shown that the bit-complexity of the compressed solution is $O(N)$ for the storage space and, if the PDE has (piecewise) constant coefficients, then also for the total number of bit-parallel operations. The compressed solution is also computed by using time $O(\log N)$ and $N/\log N$ bit-serial processors. The known bounds on the bit-complexity (for both sequential time and storage space) were at least $N\log N$; moreover, the order of $N\log N$ bit-serial processors was required to support the $O(\log N)$ parallel time in the known algorithms. It is believed that this is the first time when the solution to a linear system has been 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).