Mathematical Sciences: Parallel, Block and Two-Stage Iterative Methods for Linear Systems

研究人员研究了在序列计算机和并行计算机上高效求解线性代数方程组的迭代方法。在一大类迭代方法中，每一次迭代都由另一组方程的解组成。如果该系统依次用迭代法求解，则称为两阶段迭代法。要研究的问题包括确定最优或接近最优内迭代次数的标准，以保证两阶段法的整体收敛。当一个矩阵被适当地分块，并且它的对角块是非奇异的时，许多经典的迭代方法可以推广到把每个子矩阵当作一个分量来处理。在MIMD并行计算机(对多个数据流执行多个指令流的计算机)上，每个对角线块可以由不同的处理器求解，只要它们可用，就使用先前迭代的组件。这些是混沌或异步并行块迭代方法。将研究它们的收敛特性以及实现细节。还将研究求解一般特征值问题的迭代方法。这些方法的实验将在不同的并行体系结构上进行。科学和工程中的一大类问题是用线性方程组来描述的。这些方程中的未知量以一种简单的方式出现。线性系统的一个例子是对建筑结构上的力的描述。在设计建筑材料时，需要计算这些力。要计算的量，称为变量或未知数，是结构特定点上的力。要描述一个大型结构，如高层建筑或桥梁，需要数百或数千个方程，但因为每个点上的力只来自几个相邻的点，所以方程相对简单。求解这类方程的一种简单迭代方法，即求未知量的值，包括对某些未知数的值进行初始近似，然后计算结构其他点上的合力的值。并行计算机只是相互通信的计算机或处理器的集合。在刚才描述的方法中，不同的处理器可以使用其他处理器已经计算出的信息，同时计算不同点上的力的值。重复这个过程，直到所有的值都满足所有的方程。这种情况，如果达到了，就叫做收敛。并非所有的迭代方法都达到收敛。在这个项目中，我们将研究能够保证收敛的迭代方法。将进行实验来测试它们。

The investigator studies iterative methods to solve linear algebraic systems of equations efficiently on both sequential and parallel computers. In a large class of iterative methods, each iteration consists of a solution of another system of equations. If that system is in turn solved by an iterative method, it is called a two-stage iterative method. Among the questions to be investigated are criteria to determine the optimal or near-optimal number of inner iterations to guarantee overall convergence of the two-stage method. When a matrix is appropriately partitioned by blocks, and its diagonal blocks are nonsingular, many of the classical iterative methods can be generalized to treat each submatrix as a component. On a MIMD parallel computer (a computer that executes multiple streams of instructions on multiple streams of data), each diagonal block can be solved by a different processor, using components of previous iterations as soon as they are available. These are chaotic or asynchronous parallel block iterative methods. Their convergence properties as well as implementation details will be studied. Iterative methods for the solution of the general eigenvalue problem will also be studied. Experiments with these methods will be performed on different parallel architectures. A large class of problems in science and enginering is described by linear systems of equations. These are equations in which the unknown quantities appear in a simple way. An example of a linear system is the description of the forces on a building structure. These forces need to be calculated to design the building materials. The quantities to be calculated, called the variables or unknowns, are the forces on particular points of the structure. To describe a big structure, such as a high-rise building or a bridge, many hundreds or thousands of equations are needed, but because the forces on each point come only from a few neighboring points, the equations are relatively simple. A simple iterative method to solve such equations, that is, to find the values of the unknowns, consists in giving an initial approximation for the values of some unknowns, and then computing the values of the resulting forces on the other points of the structure. Parallel computers are simply a collection of computers or processors that communicate with each other. In the method just described, different processors can compute the value of the forces on different points simultaneously, using the information already computed by the other processors. This is repeated until all values satisfy all equations. This situation, if attained, is called convergence. Not all iterative methods attain convergence. In this project, the iterative methods for which convergence can be guaranteed will be studied. Experiments will be carried out to test them.