Design and implementation of parallel approximate inverse classes using OpenMP

A new parallel normalized optimized approximate inverse algorithm, based on the concept of antidiagonal wave pattern, for computing classes of explicitly approximate inverses, is introduced for symmetric multiprocessor systems. The parallel normalized explicit approximate inverses are used in conjunction with parallel normalized explicit preconditioned conjugate gradient schemes for the efficient solution of finite element sparse linear systems. The parallel design and implementation issues of the new algorithm are discussed and the parallel performance is presented using OpenMP. Copyright © 2008 John Wiley & Sons, Ltd.     

High Performance Inverse Preconditioning

The derivation of parallel numerical algorithms for solving sparse linear systems on modern computer systems and software platforms has attracted the attention of many researchers over the years. In this paper we present an overview on the design issues of parallel approximate inverse matrix algorithms, based on an anti-diagonal “wave pattern” approach and a “fish-bone” computational procedure, for computing explicitly various families of exact and approximate inverses for solving sparse linear systems. Parallel preconditioned conjugate gradient-type schemes in conjunction with parallel approximate inverses are presented for the efficient solution of sparse linear systems. Applications of the proposed parallel methods by solving characteristic sparse linear systems on symmetric multiprocessor systems and distributed systems are discussed and the parallel performance of the proposed schemes is given, using MPI, OpenMP and Java multithreading.     

On some ways of approximating inverses of banded matrices in connection with deriving preconditioners based on incomplete block factorizations

A unified approach of deriving band approximate inverses of band symmetric positive definite matrices is considered. Such band approximations to the inverses of successive Schur complements are required throughout incomplete block factorizations of block-tridiagonal matrices. Such block-tridiagonal matrices arise, for example, in finite element solution of second order elliptic differential equations. A sharp decay rate estimate for inverses of blocktridiagonal symmetric positive definite matrices is given in addition. Numerical tests on a number of model elliptic boundary value problems are presented comparing thus derived preconditioning matrices.     

On the numerical modeling of convection-diffusion problems by finite element multigrid preconditioning methods

During the last decades, multigrid methods have been extensively used in order to solve large scale linear systems derived from the discretization of partial differential equations using the finite difference method. The effectiveness of the multigrid method can be also exploited by using the finite element method. Finite Element Approximate Inverses in conjunction with Richardon’s iterative method could be used as smoothers in the multigrid method. Thus, a new class of smoothers based on approximate inverses can be derived. Effectiveness of explicit approximate inverses relies in the fact that they are close approximants to the inverse of the coefficient matrix and are fast to compute in parallel. Furthermore, the proposed class of finite element approximate inverses in conjunction with the explicit preconditioned Richardson method yield improved results against the classic smoothers such as Jacobi method. Moreover, a dynamic relaxation scheme is proposed based on the Dynamic Over/Under Relaxation (DOUR) algorithm. Furthermore, results for multigrid preconditioned Krylov subspace methods, such as GMRES(res), IDR(s) and BiCGSTAB based on approximate inverse smoothing and a dynamic relaxation technique are presented for the steady-state convection-diffusion equation.     

A parallel Self Mesh-Adaptive N-body method based on approximate inverses

A new parallel Self Mesh-Adaptive N-body method based on approximate inverses is proposed. The scheme is a three-dimensional Cartesian-based method that solves the Poisson equation directly in physical space, using modified multipole expansion formulas for the boundary conditions. Moreover, adaptive-mesh techniques are utilized to form a class of separate smaller n-body problems that can be solved in parallel and increase the total resolution of the system. The solution method is based on multigrid method in conjunction with the symmetric factored approximate sparse inverse matrix as smoother. The design of the parallel Self Mesh-Adaptive method along with discussion on implementation issues for shared memory computer systems is presented. The new parallel method is evaluated through a series of benchmark simulations using N-body models of isolated galaxies or galaxies interacting with dwarf companions. Furthermore, numerical results on the performance and the speedups of the scheme are presented.     

Explicit isomorphic iterative methods for solving arrow-type linear systems

A new class of approximate inverse arrow-type matrix techniques based on the concept of sparse approximate LU-type factorization procedures is introduced for computing explicitly approximate inverses without inverting the decomposition factors. Isomorphic methods in conjunction with explicit preconditioned schemes based on approximate inverse matrix techniques are presented for the efficient solution of arrow-type linear systems. Applications of the proposed method on linear systems is discussed and numerical results are given     

A rapid method of approximating the asymptote to an iterative sequence

We discuss a procedure for the adaptive construction of sparse approximate inverse preconditionings for general sparse linear systems. The approximate inverses are based on minimizing a consistent norm of the difference between the identity and the preconditioned matrix. The analysis provides positive definiteness and condition number estimates for the preconditioned system under certain circumstances. We show that for the 1-norm, restricting the size of the difference matrix below 1 may require dense approximate inverses. However, this requirement does not hold for the 2-norm, and similarly reducing the Frobenius norm below 1 does not generally require that much fill-in. Moreover, for the Frobenius norm, the calculation of the approximate inverses yields naturally column-oriented parallelism. General sparsity can be exploited in a straightforward fashion. Numerical criteria are considered for determining which columns of the sparse approximate inverse require additional fill-in. Spare algorithms are discussed for the location of potential fill-in within each column. Results using a minimum-residual-type iterative method are presented to illustrate the potential of the method.     

Explicit preconditioned iterative methods for solving large unsymmetric finite element systems

A class of Generalized Approximate Inverse Matrix (GAIM) techniques, based on the concept of LU-sparse factorization procedures, is introduced for computing explicitly approximate inverses of large sparse unsymmetric matrices of irregular structure, without inverting the decomposition factors. Explicit preconditioned iterative methods, in conjunction with modified forms of the GAIM techniques, are presented for solving numerically initial/boundary value problems on multiprocessor systems. Application of the new methods on linear boundary-value problems is discussed and numerical results are given.     

Normalized explicit finite element approximate inverse preconditioning

Normalized explicit approximate inverse matrix techniques for computing explicitly various families of normalized approximate inverses based on normalized approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference and finite element discretization of partial differential equations are presented. Normalized explicit preconditioned conjugate gradient-type schemes in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear systems. Theoretical estimates on the rate of convergence and computational complexity of the normalized 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.     

Sequential decomposition of the matrix Riccati equation and its application to the linear quadratic regulator problem

The differential matrix Riccati equation for the multi-input-multi-output linear quadratic optimal regulator problem is considered. Two methods are presented, successive and parallel, that decompose this equation into a set of Riccati equations that correspond to optimal regulator problems of possibly reduced dimensions. The additivity of the solutions to the equations obtained by the successive sequential decomposition method (SDM) and the additivity of the inverses of the solutions to the equations obtained by the parallel SDM are established. Some duality relations between the successive and the parallel methods are presented via the use of the adjoint Riccati equation. The theory developed is extended to the algebraic matrix Riccati equation as a limiting case. The application of the SDMs in the infinite-time linear quadratic regulator problem is investigated. Special attention is paid to the partially ‘cheap’ problem where the cost of some of the regulator controls or of their combinations tends asymptotically to zero. Explicit expressions for the asymptotic optimal cost are derived and the behaviour of the asymptotic optimal root loci is investigated.     

Stability investigation for linear periodic time-delayed systems using Fredholm theory

A single-loop linear periodic system with time delay is considered. Using the mathematical tool of integral Fredholm equations of the second kind, a characteristic function is constructed, the roots of which are inverses of the multipliers of the system. Rigorous sufficient stability conditions are given, which are based on approximate representation of the characteristic function in the form of a polynomial.     

On the Solution of Boundary Value Problems by Using Fast Generalized Approximate Inverse Banded Matrix Techniques

A class of finite difference schemes in conjunction with approximate inverse banded matrix techniques based on the concept of LU-type factorization procedures is introduced for computing fast explicit approximate inverses. Explicit preconditioned iterative schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of banded linear systems. A theorem on the rate of convergence and estimates of the computational complexity required to reduce the L-norm of the error is presented. Applications of the method on linear and non-linear systems are discussed and numerical results are given.     

两种A／D转换新方法--流水并行式和流水逐次逼近比较式

提出了两种新型模数转换方法。结合时序分析,全面阐明了它们的转换原理。给出了转换时间tc、比特数n和器件内部单元数m三者的数学表达式。对比现行的并行式、逐次逼近比较式和流水式模数转换方法,本文的两种新方法上仍重要的优良特性。基于第一种新方法的流不并行式ADC电路,其m和n的关系优于并行式ADC,并且比流水式ADC易于实现。基于第二种新方法的流水逐次逼近比较式ADC电路,其tc和n的关系优于逐次逼近比较式ADC,并且比流水式ADC易于实现。     

Numerical solution of three-dimensional boundary-value problems by generalized approximate inverse matrix techniques

Generalized Approximate Inverse Matrix (GAIM) techniques based on the concept of LU-type sparse factorization procedures are introduced for calculating explicitly approximate inverses of large sparse unsymmetric matrices of regular structure without inverting the factors L and U. Explicit first and second-order iterative methods in conjunction with modified forms of the GAIM techniques are presented for solving numerically three-dimensional initial/boundary-value problems on multiprocessor systems. Applications of the new methods on a 3D boundary-value problem is discussed and numerical results are given.     

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.     

Factorized Sparse Approximate Inverses for Preconditioning

In recent papers the use of sparse approximate inverses for the preconditioning of linear equations Ax=b is examined. The minimization of ||AM–I|| in the Frobenius norm generates good preconditioners without any a priori knowledge on the pattern of M. For symmetric positive definite A and a given a priori pattern there exist methods for computing factorized sparse approximate inverses L with LL ^T A ^–1. Here, we want to modify these algorithms that they are able to capture automatically a promising pattern for L.We use these approximate inverses for solving linear equations with the cg-method. Furthermore we introduce and test modifications of this method for computing factorized sparse approximate inverses.     

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.     

Comparison of four gradient-learning algorithms for neural network Wiener models

A gradient-based approach to training neural network Wiener models is presented. Calculation of the gradient or approximate gradient for the series-parallel and parallel Wiener models by the backpropagation, the sensitivity method (SM) and the backpropagation through time (BPTT) is considered in a unified framework. Four different recursive learning algorithms are derived, analysed and compared. For the truncated BPTT, it is shown that the determination of the number of unfolding time steps can be made on the basis of an impulse response function of sensitivity models. Analysis of the computational complexity of these algorithms shows that, contrary to the other recurrent neural network models, computation of the gradient in parallel Wiener models with the sensitivity method or backpropagation through time requires only a little more computational burden than the backpropagation. A simulated data example and a real data example of a laboratory two-tank system are also included to make comparison of different methods and their effectiveness and practical feasibility are shown.     

Java multithreading‐based parallel approximate arrow‐type inverses

A new parallel shared memory Java multithreaded design and implementation of the explicit approximate inverse preconditioning, for efficiently solving arrow‐type linear systems on symmetric multiprocessor systems (SMPs), is presented. A new parallel algorithm for computing a class of optimized approximate arrow‐type inverse matrix is introduced. The performance on an SMP, using Java multithreading, is investigated by solving arrow‐type linear systems and numerical results are given. The parallel performance of the construction of the optimized approximate inverse and the explicit preconditioned generalized conjugate gradient square scheme, using a dynamic workload scheduling, is also presented. Copyright © 2007 John Wiley & Sons, Ltd.     

Computing Exact Bounds on Elements of an Inverse Interval Matrix is NP-Hard

For a given interval matrix, it would be valuable to have a practical method for determining the family of matrices which are inverses of its members. Since the exact family of inverse matrices can be difficult to find or to describe, effort is often applied to developing methods for determining matrix families with interval structure which "best" approximate or contain it. A common approach is to seek exact bounds on individual elements. In this paper, we show that computing exact bounds is NP-hard; therefore any algorithm will have at least exponential-time worst-case computational cost unless P = NP.