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.     

Explicit semi-direct methods based on approximate inverse matrix techniques for solving boundary-value problems on parallel processors

Generalized approximate inverse matrix techniques and sparse Gauss-Jordan elimination procedures based on the concept of sparse product form of the inverse are introduced for calculating explicitly approximate inverses of large sparse unsymmetric (n × n) matrices. Explicit first and second order semi-direct methods in conjunction with the derived approximate inverse matrix techniques are presented for solving Parabolic and Elliptic difference equations on parallel processors. Application of the new methods on a 2D-model problem is discussed and numerical results are given.     

Matching high performance approximate inverse preconditioning to architectural platforms

In this paper we examine the performance of parallel approximate inverse preconditioning for solving finite element systems, using a variety of clusters containing the Message Passing Interface (MPI) communication library, the Globus toolkit and the Open MPI open-source software. The techniques outlined in this paper contain parameters that can be varied so as to tune the execution to the underlying platform. These parameters include the number of CPUs, the order of the linear system (n) and the “retention parameter” (δ l) of the approximate inverse used as a preconditioner. Numerical results are presented for solving finite element sparse linear systems on platforms with various CPU types and number, different compilers, different File System types, different MPI implementations and different memory sizes.

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.     

Factored approximate inverse preconditioners with dynamic sparsity patterns

We propose two sparsity pattern selection algorithms for factored approximate inverse preconditioners to solve general sparse matrices. The sparsity pattern is adaptively updated in the construction phase by using combined information of the inverse and original triangular factors of the original matrix. In order to determine the sparsity pattern, our first algorithm uses the norm of the inverse factors multiplied by the largest absolute value of the original factors, and the second employs the norm of the inverse factors divided by the norm of the original factors. Experimental results show that these algorithms improve the robustness of the preconditioners to solve general sparse matrices.     

螺旋锥束CT重建的近似逆算法

三维螺旋锥束CT以扫描速度快、成像分辨率高等诸多优点成为现代CT技术的一个重要发展方向。Katsevich精确FBP算法的提出,使得三维锥束CT研究获得了突破性进展。由于该算法的复杂性,应用中受到了限制。研究了Katsevich算法在检测板上沿滤波线展开的形式,其滤波运算由Hilbert核函数构成,利用近似逆的思想提出了融合的CT重建算法。该算法将Katsevich公式改写成近似逆的形式,得到了重建核的具体形式。     

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.     

$$\mathcal $$-FAINV: hierarchically factored approximate inverse preconditioners

Given a sparse matrix, its LU-factors, inverse and inverse factors typically suffer from substantial fill-in, leading to non-optimal complexities in their computation as well as their storage. In the past, several computationally efficient methods have been developed to compute approximations to these otherwise rather dense matrices. Many of these approaches are based on approximations through sparse matrices, leading to well-known ILU, sparse approximate inverse or factored sparse approximate inverse techniques and their variants. A different approximation approach is based on blockwise low rank approximations and is realized, for example, through hierarchical (\(\mathcal H\)-) matrices. While \(\mathcal H\)-inverses and \(\mathcal H\)-LU factors have been discussed in the literature, this paper will consider the construction of an approximation of the factored inverse through \(\mathcal H\)-matrices (\(\mathcal H\)-FAINV). We will describe a blockwise approach that permits to replace (exact) matrix arithmetic through approximate efficient \(\mathcal H\)-arithmetic. We conclude with numerical results in which we use approximate factored inverses as preconditioners in the iterative solution of the discretized convection–diffusion problem.     

A class of approximate inverse preconditioners for solving linear systems

Some preconditioners for accelerating the classical iterative methods are given in Zhang et al. [Y. Zhang and T.Z. Huang, A class of optimal preconditioners and their applications, Proceedings of the Seventh International Conference on Matrix Theory and Its Applications in China, 2006. Y. Zhang, T.Z. Huang, and X.P. Liu, Modified iterative methods for nonnegative matrices and M-matrices linear systems, Comput. Math. Appl. 50 (2005), pp. 1587–1602. Y. Zhang, T.Z. Huang, X.P. Liu, A class of preconditioners based on the (I+S(α))-type preconditioning matrices for solving linear systems, Appl. Math. Comp. 189 (2007), pp. 1737–1748]. Another kind of preconditioners approximating the inverse of a symmetric positive definite matrix was given in Simons and Yao [G. Simons, Y. Yao, Approximating the inverse of a symmetric positive definite matrix, Linear Algebra Appl. 281 (1998), pp. 97–103]. Zhang et al. ’s preconditioners and Simons and Yao's are generalized in this paper. These preconditioners are all of low construction cost, which all could be taken as approximate inverse of M-matrices. Numerical experiments of these preconditioners applied with Krylov subspace methods show the effectiveness and performance, which also show that the preconditioners proposed in this paper are better approximate inverse for M-matrices than Simons’.     

Approximate inverse preconditioning for the fast multipole BEM in acoustics

Abstact Acoustic radiation from vibrating structures is simulated by a Galerkin boundary element method based on the Burton–Miller approach. The boundary element operators are evaluated by the fast multipole method that allows large-scale computations in the medium frequency range. Two iterative solvers are considered: the generalized minimal residual method and a multigrid solver. Both approaches can be accelerated greatly by the presented approximate inverse preconditioner. Communicated by: U. Langer Research of the author is supported by the Deutsche Forschungsgemeinschaft in the framework of the collaborative research centre SFB 404 “Multifield Problems in Solid and Fluid Mechanics”     

非静力模式GRAPES的预条件技术研究

GRAPES是中国气象科学研究院研制的一个非静力格点模式,该模式以大气运动的全可压运动方程为基础,采用半隐半Lagrange方案。在模式积分中,每个时间步需要求解关于气压梯度力的三维离散Helmholtz方程,该方程组的求解在整个数值模拟时间中占70%左右,为加速求解过程,采用高效预条件技术是必然选择。将提出的多行双门槛不完全分解预条件与国内外常用的多种其他预条件技术进行了比较,同时,考查了针对不完全分解预条件的加性Schwarz与基于因子组合的两种并行化预条件技术,结果发现,多行双门槛不完全分解预条件优于包括ILUT在内的其他不完全分解预条件,且加性Schwarz略优于基于因子组合的并行预条件技术。     

Real-time inverse kinematics techniques for anthropomorphic limbs

In this paper we develop a set of inverse kinematics algorithms suitable for an anthropomorphic arm or leg. We use a combination of analytical and numerical methods to solve generalized inverse kinematics problems including position, orientation, and aiming constraints. Our combination of analytical and numerical methods results in faster and more reliable algorithms than conventional inverse Jacobian and optimization-based techniques. Additionally, unlike conventional numerical algorithms, our methods allow the user to interactively explore all possible solutions using an intuitive set of parameters that define the redundancy of the system.     

The effect of orderings on sparse approximate inverse preconditioners for non-symmetric problems

We experimentally study how reordering techniques affect the rate of convergence of preconditioned Krylov subspace methods for non-symmetric sparse linear systems, where the preconditioner is a sparse approximate inverse. In addition, we show how the reordering reduces the number of entries in the approximate inverse and thus, the amount of storage and computation required for a given accuracy. These properties are illustrated with several numerical experiments taken from the discretization of PDEs by a finite element method and from a standard matrix collection.     

A novel neural approximate inverse control for unknown nonlinear discrete dynamical systems.

A novel neural approximate inverse control is proposed for general unknown single-input-single-output (SISO) and multi-input-multi-output (MIMO) nonlinear discrete dynamical systems. Based on an innovative input/output (I/O) approximation of neural network nonlinear models, the neural inverse control law can be derived directly and its implementation for an unknown process is straightforward. Only a general identification technique is involved in both model development and control design without extra training (online or offline) for the neural nonlinear inverse controller. With less approximation made on controller development, the control will be more robust to large variations in the operating region. The robustness of the stability and the performance of a closed-loop system can be rigorously established even if the nonlinear plant is of not well defined relative degree. Extensive simulations demonstrate the performance of the proposed neural inverse control.     

An approximate inverse system for nonminimum-phase systems and its application to disturbance observer

This paper proposes an approximate inverse system for nonminimum-phase dynamical systems based on the least-square approximation method. The nonminimum-phase systems are approximated by minimum-phase systems. The proposed formulation is applied to the disturbance observation problems for multivariable nonminimum-phase systems with arbitrary relative degrees. The disturbances, which are assumed bounded, are the combination of the external disturbances, the nonlinearities and the model uncertainties of the system. The estimation error of the disturbances is controlled by the design parameters. Furthermore, the accuracy of the estimation also depends on the frequencies of the disturbances. Simulation results show the effectiveness of the proposed method.     

Execution and optimization techniques for approximate queries in heterogeneous systems

High-level queries can be used for describing scenarios of complicated analytical processing in environments of distributed heterogeneous information resources. Simultaneous abrupt increase in volume and variety of data types available for mass processing in information networks and toughening of requirements on time spent for analyzing them resulted in the need of revising the known query execution and optimization methods. In this survey, approaches to the execution and optimization of high-level precise and approximate queries are considered; unresolved problems and possible ways to solve them are also discussed.     

Regularization techniques for ill-posed inverse problems in data assimilation

Optimal state estimation from given observations of a dynamical system by data assimilation is generally an ill-posed inverse problem. In order to solve the problem, a standard Tikhonov, or L₂, regularization is used, based on certain statistical assumptions on the errors in the data. The regularization term constrains the estimate of the state to remain close to a prior estimate. In the presence of model error, this approach does not capture the initial state of the system accurately, as the initial state estimate is derived by minimizing the average error between the model predictions and the observations over a time window. Here we examine an alternative L₁ regularization technique that has proved valuable in image processing. We show that for examples of flow with sharp fronts and shocks, the L₁ regularization technique performs more accurately than standard L₂ regularization.     

A review of deterministic approximate inference techniques for Bayesian machine learning

A central task of Bayesian machine learning is to infer the posterior distribution of hidden random variables given observations and calculate expectations with respect to this distribution. However, this is often computationally intractable so that people have to seek approximation schemes. Deterministic approximate inference techniques are an alternative of the stochastic approximate inference methods based on numerical sampling, namely Monte Carlo techniques, and during the last 15 years, many advancements in this field have been made. This paper reviews typical deterministic approximate inference techniques, some of which are very recent and need further explorations. With an aim to promote research in deterministic approximate inference, we also attempt to identify open problems that may be helpful for future investigations in this field.     

Parameterizing robust manipulator controllers under approximate inverse dynamics: A double‐Youla approach

We consider the goal of ensuring robust stability when a given manipulator feedback control law is modified online, for example, to safely improve the performance by a learning module. To this end, the factorization approach is applied to both the plant and controller models to characterize robustly stabilizing controllers for rigid‐body manipulators under approximate inverse dynamics control. Outer‐loop controllers to stabilize the nonlinear uncertain loop that results from approximate inverse dynamics are often derived by lumping uncertainty in a single term and subsequent analysis of the error system. Here, by contrast, the well‐known norm bounds of these uncertain dynamics are first recast into a generalized plant configuration that preserves the characteristic uncertainty structure. Then, the overall loop uncertainty is expressed with respect to the nominal outer‐loop feedback controller by means of an uncertain dual‐Youla operator. Therefore, using the dual‐Youla parameterization, we provide a novel way to rigorously quantify permissible perturbations of robot manipulator feedforward/feedback controllers. The method proposed in this paper does not constitute another robust control law for rigid‐body manipulators, but rather a characterization of a set of robustly stabilizing controllers. The resulting double‐Youla parameterization for the control of robot manipulators is amenable to numerous advanced design methods. The result is thoroughly discussed by a planar elbow manipulator and exemplified with a six‐degree‐of‐freedom robot scenario with varying payload.