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.     

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.     

$$\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”     

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.     

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.     

Empirical analysis and evaluation of approximate techniques for pruning regression bagging ensembles

Identifying the optimal subset of regressors in a regression bagging ensemble is a difficult task that has exponential cost in the size of the ensemble. In this article we analyze two approximate techniques especially devised to address this problem. The first strategy constructs a relaxed version of the problem that can be solved using semidefinite programming. The second one is based on modifying the order of aggregation of the regressors. Ordered aggregation is a simple forward selection algorithm that incorporates at each step the regressor that reduces the training error of the current subensemble the most. Both techniques can be used to identify subensembles that are close to the optimal ones, which can be obtained by exhaustive search at a larger computational cost. Experiments in a wide variety of synthetic and real-world regression problems show that pruned ensembles composed of only 20% of the initial regressors often have better generalization performance than the original bagging ensembles. These improvements are due to a reduction in the bias and the covariance components of the generalization error. Subensembles obtained using either SDP or ordered aggregation generally outperform subensembles obtained by other ensemble pruning methods and ensembles generated by the Adaboost.R2 algorithm, negative correlation learning or regularized linear stacked generalization. Ordered aggregation has a slightly better overall performance than SDP in the problems investigated. However, the difference is not statistically significant. Ordered aggregation has the further advantage that it produces a nested sequence of near-optimal subensembles of increasing size with no additional computational cost.     

The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids

An abstract framework ofauxiliary space method is proposed and, as an application, an optimal multigrid technique is developed for general unstructured grids. The auxiliary space method is a (nonnested) two level preconditioning technique based on a simple relaxation scheme (smoother) and an auxiliary space (that may be roughly understood as a nonnested coarser space). An optimal multigrid preconditioner is then obtained for a discretized partial differential operator defined on an unstructured grid by using an auxiliary space defined on a more structured grid in which a furthernested multigrid method can be naturally applied. This new technique makes it possible to apply multigrid methods to general unstructured grids without too much more programming effort than traditional solution methods. Some simple examples are also given to illustrate the abstract theory and for instance the Morley finite element space is used as an auxiliary space to construct a preconditioner for Argyris element for biharmonic equations. Some numerical results are also given to demonstrate the efficiency of using structured grid for auxiliary space to precondition unstructured grids.     

Comparison of Krylov subspace methods with preconditioning techniques for solving boundary value problems

In this paper, we made an attempt to establish the usefulness of Lanczos solver with preconditioning technique over the preconditioned Conjugate Gradient (CG) solvers. We have presented here a detail comparative study with respect to convergence, speed as well as CPU-time, by considering appropriate boundary value problems.     

Estimation of model parameters in nonlocal damage theories by inverse analysis techniques

The parameters identification problem of the gradient-enhanced continuum damage model is examined by means of an inverse analysis. Different related issues are analyzed: (i) the investigation of the limits of applicability and predictability of the adopted numerical model and (ii) the problem of objectively extracting material properties from a structural response.A necessary condition for an adequate identification of the model parameters is the well-posedness of the inverse problem. The results show that this requirement is obtained only if additional averaged local experimental information is involved in the inverse procedure, in addition to the global structural force-deformation response. Moreover, the adopted numerical model reveals limitations in predicting the entire size effect curve of tensile tests on dog-bone-shaped concrete specimens.