To overcome difficulties in polynomial evaluation caused by overflow or unnecessary underflow, we introduce a simple scaling procedure into Horner's method.

For multiprocessor systems with two level memory hierarchy; the communication requirements of parallel Cholesky factorization of dense and sparse symmetric, positive definite matrices are analyzed. The data traffic associated with computing the Chloesky factor of an nn ×n dense matrix using nα processors, α ≤ 2, is shown to be Ω(n2+α/2), assuming that the computational load is uniformly distributed. For an nn ×n sparse matrix, representing a √n × √n regular grid graph, the corresponding data traffic is shown to be Ω(n1+α/2), α ≤ 1.

Given a discretization stencil, partitioning the problem domain is an important first step for the efficient solution of partial differential equations on multiple processor systems. We derive partitions that minimize interprocessor communication when the number of processors is known a priori and each domain partition is assigned to a different processor. Our partitioning technique uses the stencil structure to select appropriate partition shapes. For square problem domains, we show that nonstandard partitions (e.g., hexagons) are frequently preferable to the standard square partitions for a variety of commonly used stencils. We conclude with a formalization of the relationship between partition shape, stencil structure, and architecture, allowing selection of optimal partitions for a variety of parallel systems.

The applicability of static data flow architectures to the iterative solution of sparse linear systems of equations is investigated. An analytic performance model of a static data flow computation is developed. This model includes both spatial parallelism, concurrent execution in multiple PEs, and pipelining, the streaming of data from array memories through the PEs. The performance model is used to analyze a row-partitioned iterative algorithms for solving sparse linear systems of algebraic equations. On the basis of this analysis, design parameters for the static data flow architecture as a function of matrix sparsity and dimension are proposed.