EFFICIENT OUT-OF-CORE ALGORITHMS FOR LINEAR RELAXATION USING BLOCKINGCOVERS

When a numerical computation fails to fit in the primary memory of a s erial or parallel computer, a so-called ''out-of-core'' algorithm, whi ch moves data between primary and secondary memories, must be used. In this paper, we study out-of-core algorithms for sparse linear relaxat ion problems in which each iteration of the algorithm updates the stal e of every vertex in a graph with a linear combination of the states o f its neighbors. We give a general method that can save substantially on the I/O traffic for ma ny problems. For example, our tech ni que al lows a computer with M words of primary memory to perform T = Omega(M- 1/5) cycles of a multigrid algorithm for a two-dimensional elliptic so lver over an n-point domain using only -(nT/M-1/5) I/O transfers, as c ompared with the naive algorithm which requires Omega(nT) I/O's. Our m ethod depends on the existence of a ''blocking'' cover of the graph th at 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. The key idea in our method is t o introduce a variable for each removed vertex for each time step of t he algorithm. We maintain linear dependences among the removed vertice s, thereby allowing each subgraph to be iteratively relaxed without ex ternal communication. We give a general theorem relating blocking cove rs to I/O-efficient relaxation schemes. We also give an automatic meth od for finding blocking covers for certain classes of graphs, includin g planar graphs and d-dimensional simplicial graphs with constant aspe ct ratio (i.e., graphs that arise from dividing d-space into ''well-sh aped'' polyhedra). As a result, we can perform T iterations of linear relaxation on any n-vertex planar graph using only -(n + nT root Ig n/ M-1/4) I/O's or on any n-node d-dimensional simplicial graph with cons tant aspect ratio using only O(n + nTlg n/M-Omega(1/d)) I/O's. (C) 199 7 Academic Press.