Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract)
Charles E. Leiserson, Satish S. Rao, Sivan Toledo · 1993
When a numerical computation fails to fit in the primary memory of a serial or parallel computer, a so-called "out-of-core" algorithm must be used which moves data between primary and secondary memories. In this paper, we study out-of-core algorithms for sparse linear relaxation problems in which each iteration of the algorithm updates the state of every vertex in a graph with a linear combination of the states of its neighbors. We give a general method that can save substantially on the I/O traffic for many problems. For example, our technique allows a computer with M words of primary memory to perform T = \\Omega\\Gamma M 1=5 ) cycles of a multigrid algorithm for a two-dimensional elliptic solver over an n-point domain using only \\Theta(nT =M 1=5 ) I/O transfers, as compared with the naive algorithm which requires\\Omega\\Gamma nT ) I/O's. Our method depends on the existence of a "blocking " cover of the graph that underlies the linear relaxation. A blocking cover has the property that the subgraphs forming the cover have large diameters once a small number of vertices have been removed from the graph. The key idea in our method is to introduce a variable for each removed vertex for each time step of the algorithm. We maintain linear dependences among the removed vertices, thereby allowing each subgraph to be iteratively relaxed without external communication. We give a general theorem relating blocking covers to I/O-efficient relaxation schemes. We also give an automatic method for finding blocking cove...