Solving 3D block bidiagonal linear systems on vector computers

摘要

Standard 7-point finite-difference discretization of second-order PDEs over a rectangular grid over a 3-dimensional block leads, with the usual lexicograpical ordering of the gridpoints, to block tridiagonal linear systems. In many popular iterative methods for the solution of these systems, triangular systems which have a block bidiagonal structure have to be solved. This is often recognized to be the major bottleneck, on vector computers, with respect to the computational speed, when carried out in a straightforward manner.In this paper we will discuss different techniques for the vectorization of the solution of 3D-block bidiagonal systems. We will report on actually observed performances for the ICCG algorithm, for which these bidiagonal systems have the reputation to spoil the overall performance, on some computers. The potentially most powerful of the vectorization techniques leads to long vector operations, at the cost, however, of strides and indirect addressing. Since the CYBER 205 is generally believed to stay behind in performance under such circumstances, we have chosen this machine to show in detail how these vectorization techniques can be implemented with almost equal performance as in the same contiguous vector case. Our methods are directly applicable to the ETA-10 family of supercomputers and may be adapted to other vector computers as well.