Domain decomposition PCG methods for serial and parallel processing

In this paper two domain decomposition formulations are presented in conjunction with the preconditioned conjugate gradient method (PCG) for the solution of large-scale problems in solid and structural mechanics. In the first approach, the PCG method is applied to the global coefficient matrix, while in the second approach it is applied to the interface problem after eliminating the internal degrees of freedom. For both implementations, a subdomain-by-subdomain (SBS) polynomial preconditioner is employed, based on local information of each subdomain. The approximate inverse of the global coefficient matrix or the Schur complement matrix, which acts as the preconditioner, is expressed by a truncated Neumann series resulting in an additive type local preconditioner. Block type preconditioning, where full elimination is performed inside each block, is also studied and compared with the proposed polynomial preconditioning.     

Preconditioning by Gram matrix approximation for diffusion–convection–reaction equations with discontinuous coefficients

This work analyses the preconditioning with Gram matrix approximation for the numerical solution of a linear convection–diffusion–reaction equation with discontinuous diffusion and reaction coefficients. The standard finite element method with piecewise linear test and trial functions on uniform meshes discretizes the equation. Three preconditioned conjugate gradient algorithms solve the discrete linear system: CGS, CGSTAB and GMRES. The preconditioning with Gram matrix approximation consists of replacing the solving of the equation with the preconditioner by two symmetric MG iterations. Numerical results are presented to assess the convergence behaviour of the preconditioning and to compare it with other preconditioners of multilevel type.     

A parallel preconditioned conjugate gradient method using domain decomposition and inexact solvers on each subdomain

We describe a preconditioned conjugate gradient solution strategy for a multiprocessor system with message passing architecture. The preconditioner combines two techniques, a Schurcomplement preconditioning over “coupling boundaries” between the subdomains and an arbitrary choice of classic preconditioning for the inner degrees of freedom on each subdomain. All computational work on the single subdomains is carried out in parallel by distributing the subdomain data over the processor network before starting the finite element solution process (including generating the element matrices and assemblying the local subdomain stiffness matrix). The resulting spectral condition number of the entire preconditioner is estimated. For the important example of choosing MIC(0)-*-preconditioning on the subdomains, the condition number obtained is essentially the product of the two condition numbers involved.     

An iterative solver for a mixed variable variational formulation of the (first) biharmonic problem

The coupled system of equations resulting from a mixed variable formulation of the biharmonic problem is solved by a preconditioned conjugate gradient method. The preconditioning matrix is based on an incomplete factorization of a positive definite operator similar to the 13-point difference approximation of the biharmonic operator.The first iterate is already quite accurate even if the initial approximation is not. Hence, often a small number of iterations will suffice to get an accurate enough solution. For smaller iteration errors the number of iterations grows as O(h^?1), h → 0, where h is an average mesh-size parameter.     

Finite elements using long vectors of the DAP

The Finite Element Method for solving partial differential equations using the long vector mode of the DAP is presented. This work was developed on a 32 × 32 version of the DAP attached to a Perq scientific workstation.

First, the implementation of finite elements using the long vector mode of the DAP is given, followed by the treatment of boundary conditions and the solution of the finite element equations using a parallel conjugate gradient method. Two solution procedures for the parallel conjugate gradient method, first without global matrix assembly and second with global matrix assembly, are presented and their advantages and disadvantages are discussed. Preconditioners for the conjugate gradient method based on iteration methods are also discussed and results include a 1-step point Jacobi preconditioner, a m-step point Jacobi preconditioner and a m-step multi-colour preconditioner. Finally long vector implementations for a larger system which stores multinodes per processor using a sliced mapping technique and domain decomposition are included.     

Additive polynomial preconditioners for parallel computers

We present a polynomial preconditioner that can be used with the conjugate gradient method to solve symmetric and positive definite systems of linear equations. Each step of the preconditioning is achieved by simultaneously taking an iteration of the SOR method and an iteration of the reverse SOR method (equations taken in reverse order) and averaging the results. This yields a symmetric preconditioner that can be implemented on parallel computers by performing the forward and reverse SOR iterations simultaneously. We give necessary and sufficient conditions for additive preconditioners to be positive definite.

We find an optimal parameter, ω, for the SOR-Additive linear stationary iterative method applied to 2-cyclic matrices. We show this method is asymptotically twice as fast as SSOR when the optimal ω is used.

We compare our preconditioner to the SSOR polynomial preconditioner for a model problem. With the optimal ω, our preconditioner was found to be as effective as the SSOR polynomial preconditioner in reducing the number of conjugate gradient iterations. Parallel implementations of both methods are discussed for vector and multiple processors. Results show that if the same number of processors are used for both preconditioners, the SSOR preconditioner is more effective. If twice as many processors are used for the SOR-Additive preconditioner, it becomes more efficient than the SSOR preconditioner when the number of equations assigned to a processor is small. These results are confirmed by the Blue Chip emulator at the University of Washington.     

Parallel and Systolic Solution of Normalized Explicit Approximate Inverse Preconditioning

A new class of normalized approximate inverse matrix techniques, based on the concept of sparse normalized approximate factorization procedures are introduced for solving sparse linear systems derived from the finite difference discretization of partial differential equations. Normalized explicit preconditioned conjugate gradient type methods in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of sparse linear systems. Theoretical results on the rate of convergence of the normalized explicit preconditioned conjugate gradient scheme and estimates of the required computational work are presented. Application of the new proposed methods on two dimensional initial/boundary value problems is discussed and numerical results are given. The parallel and systolic implementation of the dominant computational part is also investigated.     

A preconditioning strategy for microwave susceptibility in ferromagnets

3D numerical simulations of ferromagnetic materials can be compared with experimental results via microwave susceptibility. In this paper, an optimised computation of this microwave susceptibility for large meshes is proposed. The microwave susceptibility is obtained by linearisation of the Landau and Lifchitz equations near equilibrium states and the linear systems to be solved are very ill-conditioned. Solutions are computed using the conjugate gradient method for the normal equation (CGN Method). An efficient preconditioner is developed consisting of a projection and an approximation of an “exact” preconditioner in the set of circulant matrices. Control of the condition number due to the preconditioning and evolution of the singular value decomposition are shown in the results.     

Algebraic multigrid methods based on element preconditioning

This paper presents a new algebraic multigrid (AMG) solution strategy for large linear systems with a sparse matrix arising from a finite element discretization of some self-adjoint, second order, scalar, elliptic partial differential equation. The AMG solver is based on Ruge/Stübens method. Ruge/Stübens algorithm is robust for M-matrices, but unfortunately the “region of robustness“ between symmetric positive definite M-matrices and general symmetric positive definite matrices is very fuzzy.

For this reason the so-called element preconditioning technique is introduced in this paper. This technique aims at the construction of an M-matrix that is spectrally equivalent to the original stiffness matrix. This is done by solving small restricted optimization problems. AMG applied to the spectrally equivalent M-matrix instead of the original stiffness matrix is then used as a preconditioner in the conjugate gradient method for solving the original problem.

The numerical experiments show the efficiency and the robustness of the new preconditioning method for a wide class of problems including problems with anisotropic elements.     

Delay point schedules for irregular parallel computations

In irregular scientific computational problems one is periodically forced to choosea delay point where some overhead cost is suffered to ensure correctness, or to improve subsequent performance. Examples of delay points are problem remappings, and global synchronizations. One sometimes has considerable latitude in choosing the placement and frequency of delay points; we consider the problem of scheduling delay points so as to minimize the overal execution time. We illustrate the problem with two examples, a regridding method which changes the problem discretization during the course of the computation, and a method for solving sparse triangular systems of linear equations. We show that one can optimally choose delay points in polynomial time using dynamic programming. However, the cost models underlying this approach are often unknown. We consequently examine a scheduling heuristic based on maximizing performance locally, and empirically show it to be nearly optimal on both problems. We explain this phenomenon analytically by identifying underlying assumptions which imply that overall performance is maximized asymptotically if local performance is maximized.This research was supported in part by the National Aeronautics and Space Administration under NASA contract NAS1-18107 while the author consulted at ICASE, Mail Stop 132C, NASA Langley Research Center, Hampton, Virginia 23665.Supported in part by NASA contract NAS1-18107, the Office of Naval Research under Contract No. N00014-86-K-0654, and NSF Grant DCR 8106181.     

A relaxed block-triangular splitting preconditioner for generalized saddle-point problems

For the generalized saddle-point problems, based on a new block-triangular splitting of the saddle-point matrix, we introduce a relaxed block-triangular splitting preconditioner to accelerate the convergence rate of the Krylov subspace methods. This new preconditioner is easily implemented since it has simple block structure. The spectral property of the preconditioned matrix is analysed. Moreover, the degree of the minimal polynomial of the preconditioned matrix is also discussed. Numerical experiments are reported to show the preconditioning effect of the new preconditioner.     

A note on the accuracy of spectral method applied to nonlinear conservation laws

Fourier spectral method can achieve exponential accuracy both on the approximation level and for solving partial differential equations if the solutions are analytic. For a linear PDE with discontinuous solutions, Fourier spectral method will produce poor point-wise accuracy without post-processing, but still maintains exponential accuracy for all moments against analytic functions. In this note we assess the accuracy of Fourier spectral method applied to nonlinear conservation laws through a numerical case study. We have found out that the moments against analytic functions are no longer very accurate. However the numerical solution does contain accurate information which can be extracted by a Gegenbauer polynomial based post-processing.Research supported by ARO Grant DAAL03-91-G-0123 and DAAH04-94-G-0205, NSF Grant DMS-9211820, NASA Grant NAG1-1145 and contract NAS1-19480 while the first author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23681-0001, and AFOSR Grant 93-0090.     

An approach for structural static reanalysis with unchanged number of degrees of freedom

This paper presents an approach for structural static reanalysis with unchanged number of degrees of freedom. Preconditioned conjugate gradient method is employed, and a new preconditioner is constructed by updating the Cholesky factorization of the initial stiffness matrix with little cost. The proposed method preserves the ease of implementation and significantly improves the quality of the results. In particular, the accuracy of the approximate solutions can adaptively be monitored. Numerical examples show that the condition number of preconditioned system using the new preconditioner is much smaller than that using the initial stiffness matrix as the preconditioner. Therefore, the fast convergence and accurate results can be obtained by the proposed approach.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Object-oriented programming of distributed iterative equation solvers

An object-oriented approach is used to develop classes and frameworks for the implementation of distributed iterative equation solution. The software is implemented using the .NET framework, and builds upon previous work by the author. Development of the framework for iterative solution makes good use of interfaces to isolate sources of complexity. The framework is used for three different solution scenarios (i) conjugate gradient iteration on a single matrix; (ii) conjugate gradient iteration when domain decomposition is used; and (iii) using the Schur complement approach. Moreover, the framework is used for both local and remote objects. The .NET framework makes it very straightforward to program distributed applications, and the object-oriented approach greatly facilitates the software development. The framework was used in a finite element program and the speed-up results are shown.     

Physically based adaptive preconditioning for early vision

Several problems in early vision have been formulated in the past in a regularization framework. These problems, when discretized, lead to large sparse linear systems. In this paper, we present a novel physically based adaptive preconditioning technique which can be used in conjunction with a conjugate gradient algorithm to dramatically improve the speed of convergence for solving the aforementioned linear systems. A preconditioner, based on the membrane spline, or the thin plate spline, or a convex combination of the two, is termed a physically based preconditioner for obvious reasons. The adaptation of the preconditioner to an early vision problem is achieved via the explicit use of the spectral characteristics of the regularization filter in conjunction with the data. This spectral function is used to modulate the frequency characteristics of a chosen wavelet basis, and these modulated values are then used in the construction of our preconditioner. We present the preconditioner construction for three different early vision problems namely, the surface reconstruction, the shape from shading, and the optical flow computation problems. Performance of the preconditioning scheme is demonstrated via experiments on synthetic and real data sets     

A parallel preconditioned conjugate gradient solution method for finite element problems with coarse–fine mesh formulation

The object of this paper is a parallel preconditioned conjugate gradient iterative solver for finite element problems with coarse-mesh/fine-mesh formulation. An efficient preconditioner is easily derived from the multigrid stiffness matrix. The method has been implemented, for the sake of comparison, both on a IBM-RISC590 and on a Quadrics-QH1, a massive parallel SIMD machine with 128 processors. Examples of solutions of simple linear elastic problems on rectangular grids are presented and convergence and parallel performance are discussed.     

A trust-region framework for managing the use of approximation models in optimization

This paper presents an analytically robust, globally convergent approach to managing the use of approximation models of varying fidelity in optimization. By robust global behaviour we mean the mathematical assurance that the iterates produced by the optimization algorithm, started at an arbitrary initial iterate, will converge to a stationary point or local optimizer for the original problem. The approach presented is based on the trust region idea from nonlinear programming and is shown to be provably convergent to a solution of the original high-fidelity problem. The proposed method for managing approximations in engineering optimization suggests ways to decide when the fidelity, and thus the cost, of the approximations might be fruitfully increased or decreased in the course of the optimization iterations. The approach is quite general. We make no assumptions on the structure of the original problem, in particular, no assumptions of convexity and separability, and place only mild requirements on the approximations. The approximations used in the framework can be of any nature appropriate to an application; for instance, they can be represented by analyses, simulations, or simple algebraic models. This paper introduces the approach and outlines the convergence analysis.This research was supported by the Dept. of Energy grant DEFG03-95ER25257 and Air Force Office of Scientific Research grant F49620-95-1-0210This research was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USAThis research was supported by the Air Force Office of Scientific Research grant F49620-95-1-0210 and by the National Aeronautics and Space Administration under NASA Contract No. NAS1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USA     

Lie and morse theory for periodic orbits of vector fields and matrix riccati equations,I: General lie-theoretic methods

The problem of finding periodic solutions of the matrix Riccati equations of linear control theory is interpreted geometrically as a problem of finding periodic orbits of certain one-parameter transformation groups on Grassmann manifolds. For certain control problems the vector fields which generate these groups can be written as a sum of two commuting vector fields, one a gradient vector field, the other a Killing vector field, i.e., an infinitesimal isometry of a metric on the Grassman manifold. For such vector fields, the methods of Morse theory can be adapted to study the periodic orbits. The topological data that is needed to count periodic orbits, i.e., the Poincare polynomial of certain submanifolds of the Grassmann manifold, can be derived from results proved by A. Borel.Research supported by the Ames Research Center (NASA), #NSG-2402, U.S. Army Research Office, #ILIG1102RHN7-05 MATH and the National Science Foundation, NASA 2384-DA 62–82, DOE CONTRACT NO. DE-AC01-8 OR A-5256.     

Fluid-structure interactions using different mesh motion techniques

In this work, we compare different mesh moving techniques for monolithically-coupled fluid-structure interactions in arbitrary Lagrangian–Eulerian coordinates. The mesh movement is realized by solving an additional partial differential equation of harmonic, linear-elastic, or biharmonic type. We examine an implementation of time discretization that is designed with finite differences. Spatial discretization is based on a Galerkin finite element method. To solve the resulting discrete nonlinear systems, a Newton method with exact Jacobian matrix is used. Our results show that the biharmonic model produces the smoothest meshes but has increased computational cost compared to the other two approaches.