Mathematical Sciences: Blocks, Partitions, Asynchronous Parallel Methods, and Applications to Markov Chains and Other Problems

小行星9625865 调查研究块和异步迭代法的有效解决方案的非对称线性代数方程组。 该项目的一个方面是研究稀疏矩阵的阈值分割算法的应用。 该项目的重点是奇异系统。 奇异方程组出现在许多应用中，包括某些类型的微分方程建模物理现象，马尔可夫链和排队模型。 使用马尔可夫链，例如，评估计算机系统的性能，而排队模型特别模拟电信网络中的业务。 该项目开发了求解线性方程组，特别是奇异系统的快速方法。 这些方法是迭代的：该方法从对系统解的初始猜测开始，产生一系列接近实际解的近似解。 用于并行计算机的异步方法是指在每个处理器中以异步方式执行部分计算的方法，即，而没有处理器之间的同步。 换句话说，每个处理器都使用在任何给定时刻可用的信息继续执行其任务，而无需等待其他处理器完成其任务。 处理器不会等待：它们保持主动计算更好的近似解。 因此，可以大大缩短整体解决方案的时间。 微分方程、马尔可夫链或排队模型的变量可以自然地划分成变量集，例如，通过网络或图的节点的近连通性。 这种划分在表示要求解的线性系统的矩阵中引入了特定的块结构。 异步并行方法非常适合处理这些块。 新的分区算法，考虑到矩阵的值进行了探讨。 许多微分方程，如某些对流扩散方程的微分，产生系数在很宽的值范围内变化的矩阵，即，有些很大，有些很小。 这些问题在实际中很难解决，大多数现代迭代方法都不能收敛。 收敛的方法非常昂贵或非常慢。 考虑到这些值的分割算法可用于置换这些矩阵，使得大系数沿着矩阵的对角线。 该置换矩阵的部分，例如，它的块沿着对角线，可以用作有效的预处理器。 初步实验表明，这种方法导致快速收敛。 因此，该项目可以提供一种有效解决科学和工程中一类重要问题的方法。

9625865 Szyld The investigator studies block and asynchronous iterative methods for the efficient solution of nonsymmetric linear algebraic systems of equations. One aspect of the project is the study of the application of threshold partitioning algorithms for sparse matrices. The emphasis of the project is on singular systems. Singular systems of equations arise in many applications, including certain types of differential equations modeling physical phenomena, Markov chains, and queuing models. Markov chains are used, e.g., to evaluate the performance of computer systems, while queuing models in particular simulate traffic in telecommunication networks. This project develops fast methods for solving linear systems of equations, particularly singular systems. The methods are iterative: starting from an initial guess at the solution of a system, the method produces a sequence of approximate solutions that approaches the actual solution. Asynchronous methods for parallel computers refer to methods in which part of the computation is performed in each processor in an asynchronous way, i.e., without synchronization between the processors. In other words, each processor proceeds with its tasks, using the information available at any given moment without waiting for the other processors to finish their tasks. Processors do not wait: they keep active computing better approximations to the solutions. Therefore the overall solution time can be greatly reduced. The variables of the differential equations, of the Markov chains, or of the queuing models, may be partitioned naturally into sets of variables, e.g., by the near-connectivity of the nodes of a network or graph. This partition induces a particular block structure in the matrix representing the linear system to be solved. Asynchronous parallel methods are well suited to deal with these blocks. New partitioning algorithms that take into account the values of the matrix are explored. The discre tizations of many differential equations, such as certain convection-diffusion equations, give rise to matrices with coefficients varying over a wide range of values, i.e., some large and some very small. These problems are very hard to solve in practice, and most modern iterative methods fail to converge. The methods that do converge are very expensive or very slow. Partitioning algorithms that take into account these values can be used to permute these matrices so that the large coefficients lie along the diagonal of the matrix. Parts of this permuted matrix, e.g., its blocks along the diagonal, can be used as an effective preconditioner. Preliminary experiments indicate that this approach leads to fast convergence. Thus, the project can provide a method to efficiently solve a class of important problems in science and engineering.