Shape reanalysis and sensitivities utilizing preconditioned iterative boundary solvers

The computational advantages associated with the utilization of preconditioned iterative equation solvers are quantified for the reanalysis of perturbed shapes using continuum structural boundary element analysis (BEA). Both single- and multizone three-dimensional problems are examined. Significant redutions in computer time are obtained by making use of previously computed solution vectors and preconditioners in subsequent analyses. The effectiveness of this technique is demonstrated for the computation of shape response sensitivities required in shape optimization. Computer times and accuracies achieved using the preconditioned iterative solvers are compared with those obtained via direct solvers and implicit differentiation of the boundary integral equations. It is concluded that this approach employing preconditioned iterative equation solvers in reanalysis and sensitivity analysis can be competitive with if not superior to those involving direct solvers.     

On the use of inexact subdomain solvers for BDDC algorithms

The standard BDDC (balancing domain decomposition by constraints) preconditioner is shown to be equivalent to a preconditioner built from a partially subassembled finite element model. This results in a system of linear algebraic equations which is much easier to solve in parallel than the fully assembled model; the cost is then often dominated by that of the problems on the subdomains. An important role is also played, both in theory and practice, by an averaging operator and in addition exact Dirichlet solvers are used on the subdomains in order to eliminate the residual in the interior of the subdomains. The use of inexact solvers for these problems and even the replacement of the Dirichlet solvers by a trivial extension are considered. It is established that one of the resulting algorithms has the same eigenvalues as the standard BDDC algorithm, and the connection of another with the FETI-DP algorithm with a lumped preconditioner is also considered. Multigrid methods are used in the experimental work and under certain assumptions, it is established that the iteration count essentially remains the same as when exact solvers are used, while considerable gains in the speed of the algorithm can be realized since the cost of the exact solvers grows superlinearly with the size of the subdomain problems while the multigrid methods are linear.     

A performance assessment of NE/Nastran's new sparse direct and iterative solvers

Noran Engineering, Inc. has recently added two new solvers, Vector Sparse Solver (VSS) and Vector Iterative Solver (VIS), to its general-purpose finite element analysis engine, NE/Nastran. One solver uses a direct approach while the other uses an iterative Preconditioned Conjugate Gradient (PCG) approach. Both solvers are fully sparse and store and operate only on nonzero matrix elements. This paper looks at the effect these solvers have on the performance of NE/Nastran for various finite element model and solution types. In many cases performance has increased by a factor of 10, thus allowing jobs that took days to be solved in minutes.     

Preconditioners for the dual-primal FETI methods on nonmatching grids: Numerical study

The FETI-DP method is a substructuring method that uses Lagrange multipliers to match the continuity condition on the subdomain boundaries. For the FETI-DP method on non-matching grids, two different formulations are known with respect to how to employ the mortar matching condition. Keeping step with the developments of the FETI-DP methods, a variety of preconditioners for the FETI-DP operator have been developed. However, there has not been any numerical study for the FETI-DP method, which compares those preconditioners on nonmatching grids while there have been a few papers for numerical study on the comparison of FETI preconditioners. Therefore, we present the numerical study of four different preconditioners for two-dimensional elliptic problems. The numerical results confirm the superiority of the preconditioner by Kim and Lee [1] for noncomparably nonmatching grids, while the superiority of the preconditioner by Dryja and Widlund [2] is confirmed for matching grids and comparably nonmatching grids.     

Parallel methods for optimality criteria-based topology optimization

Topology optimization problems require the repeated solution of finite element problems that are often extremely ill-conditioned due to highly heterogeneous material distributions. This makes the use of iterative linear solvers inefficient unless appropriate preconditioning is used. Even then, the solution time for topology optimization problems is typically very high. These problems are addressed by considering the use of non-overlapping domain decomposition-based parallel methods for the solution of topology optimization problems. The parallel algorithms presented here are based on the solid isotropic material with penalization (SIMP) formulation of the topology optimization problem and use the optimality criteria method for iterative optimization. We consider three parallel linear solvers to solve the equilibrium problem at each step of the iterative optimization procedure. These include two preconditioned conjugate gradient (PCG) methods: one using a diagonal preconditioner and one using an incomplete LU factorization preconditioner with a drop tolerance. A third substructuring solver that employs a hybrid of direct and iterative (PCG) techniques is also studied. This solver is found to be the most effective of the three solvers studied, both in terms of parallel efficiency and in terms of its ability to mitigate the effects of ill-conditioning. In addition to examining parallel linear solvers, we consider the parallelization of the iterative optimality criteria method. To tackle checkerboarding and mesh dependence, we propose a multi-pass filtering technique that limits the number of “ghost” elements that need to be exchanged across interprocessor boundaries.     

Algebraic and Parametric Solvers for the Power Flow Problem: Towards Real-Time and Accuracy-Guaranteed Simulation of Electric Systems

The power flow model performs the analysis of electric distribution and transmission systems. With this statement at hand, in this work we present a summary of those solvers for the power flow equations, in both algebraic and parametric version. The application of the Alternating Search Direction method to the power flow problem is also detailed. This results in a family of iterative solvers that combined with Proper Generalized Decomposition technique allows to solve the parametric version of the equations. Once the solution is computed using this strategy, analyzing the network state or solving optimization problems, with inclusion of generation in real-time, becomes a straightforward procedure since the parametric solution is available. Complementing this approach, an error strategy is implemented at each step of the iterative solver. Thus, error indicators are used as an stopping criteria controlling the accuracy of the approximation during the construction process. The application of these methods to the model IEEE 57-bus network is taken as a numerical illustration.     

Fast Nonlinear Least Squares Optimization of Large-Scale Semi-Sparse Problems

Many problems in computer graphics and vision can be formulated as a nonlinear least squares optimization problem, for which numerous off-the-shelf solvers are readily available. Depending on the structure of the problem, however, existing solvers may be more or less suitable, and in some cases the solution comes at the cost of lengthy convergence times. One such case is semi-sparse optimization problems, emerging for example in localized facial performance reconstruction, where the nonlinear least squares problem can be composed of hundreds of thousands of cost functions, each one involving many of the optimization parameters. While such problems can be solved with existing solvers, the computation time can severely hinder the applicability of these methods. We introduce a novel iterative solver for nonlinear least squares optimization of large-scale semi-sparse problems. We use the nonlinear Levenberg-Marquardt method to locally linearize the problem in parallel, based on its first-order approximation. Then, we decompose the linear problem in small blocks, using the local Schur complement, leading to a more compact linear system without loss of information. The resulting system is dense but its size is small enough to be solved using a parallel direct method in a short amount of time. The main benefit we get by using such an approach is that the overall optimization process is entirely parallel and scalable, making it suitable to be mapped onto graphics hardware (GPU). By using our minimizer, results are obtained up to one order of magnitude faster than other existing solvers, without sacrificing the generality and the accuracy of the model. We provide a detailed analysis of our approach and validate our results with the application of performance-based facial capture using a recently-proposed anatomical local face deformation model.     

On the parallel iterative solution of linear systems arising in the FEAST algorithm for computing inner eigenvalues

Methods for the solution of sparse eigenvalue problems that are based on spectral projectors and contour integration have recently attracted more and more attention. Such methods require the solution of many shifted sparse linear systems of full size. In most of the literature concerning these eigenvalue solvers, only few words are said on the solution of the linear systems, but they turn out to be very hard to solve by iterative linear solvers in practice. In this work we identify a row projection method for the solution of the inner linear systems encountered in the FEAST algorithm and introduce a novel hybrid parallel and fully iterative implementation of the eigenvalue solver. Our approach ultimately aims at achieving extreme parallelism by exploiting the algorithm’s potential on several levels. We present numerical examples where graphene modeling is one of the target applications. In this application, several hundred or even thousands of eigenvalues from the interior of the spectrum are required, which is a big challenge for state-of-the-art numerical methods.     

Tailored least-squares solvers implementation for high-performance gravity field research

Least-squares (LS) problems occur in almost every scientific and engineering discipline. Basically, they are generated by providing more observations than unknown parameters to be resolved. Appropriate LS solvers depend on both quality and computational issues. With regard to the latter, this paper focuses on the tailored parallel implementation of two LS solvers: the iterative LSQR method (substitutional for any Krylov-space method) and the “brute-force” inversion approach. Both implementations demonstrate very good scaling results in a parallel processing environment. Even so, the present investigations show that, from the computational and hardware point of view, iterative solvers outperform the “brute-force” approach. LSQR not only provides superior speed-up values; but, in addition, source code portability and hardware requirements are much more convenient for the iterative solver. These conclusions are drawn in the context of state-of-the-art terrestrial geopotential recovery with regard to the forthcoming Gravity field and steady-state Ocean Circulation Explorer (GOCE) satellite mission.     

Multi-period portfolio optimization with linear control policies

This paper is concerned with multi-period sequential decision problems for financial asset allocation. A model is proposed in which periodic optimal portfolio adjustments are determined with the objective of minimizing a cumulative risk measure over the investment horizon, while satisfying portfolio diversity constraints at each period and achieving or exceeding a desired terminal expected wealth target. The proposed solution approach is based on a specific affine parameterization of the recourse policy, which allows us to obtain a sub-optimal but exact and explicit problem formulation in terms of a convex quadratic program.In contrast to the mainstream stochastic programming approach to multi-period optimization, which has the drawback of being computationally intractable, the proposed setup leads to optimization problems that can be solved efficiently with currently available convex quadratic programming solvers, enabling the user to effectively attack multi-stage decision problems with many securities and periods.     

A Least-Squares/Relaxation Method for the Numerical Solution of the Three-Dimensional Elliptic Monge–Ampère Equation

In this article, we address the numerical solution of the Dirichlet problem for the three-dimensional elliptic Monge–Ampère equation using a least-squares/relaxation approach. The relaxation algorithm allows the decoupling of the differential operators from the nonlinearities. Dedicated numerical solvers are derived for the efficient solution of the local optimization problems with cubicly nonlinear equality constraints. The approximation relies on mixed low order finite element methods with regularization techniques. The results of numerical experiments show the convergence of our relaxation method to a convex classical solution if such a solution exists; otherwise they show convergence to a generalized solution in a least-squares sense. These results show also the robustness of our methodology and its ability at handling curved boundaries and non-convex domains.     

Don’t care in SMT: building flexible yet efficient abstraction/refinement solvers

This paper describes a method for combining “off-the-shelf” SAT and constraint solvers for building an efficient Satisfiability Modulo Theories (SMT) solver for a wide range of theories. Our method follows the abstraction/refinement approach to simplify the implementation of custom SMT solvers. The expected performance penalty by not using an interweaved combination of SAT and theory solvers is reduced by generalising a Boolean solution of an SMT problem first via assigning don’t care to as many variables as possible. We then use the generalised solution to determine a thereby smaller constraint set to be handed over to the constraint solver for a background theory. We show that for many benchmarks and real-world problems, this optimisation results in considerably smaller and less complex constraint problems. The presented approach is particularly useful for assembling a practically viable SMT solver quickly, when neither a suitable SMT solver nor a corresponding incremental theory solver is available. We have implemented our approach in the ABsolver framework and applied the resulting solver successfully to an industrial case-study: the verification problems arising in verifying an electronic car steering control system impose non-linear arithmetic constraints, which do not fall into the domain of any other available solver.     

Hybrid approach for solving systems of nonlinear equations using chaos optimization and quasi-Newton method

Solving systems of nonlinear equations is one of the most difficult numerical computation problems. The convergences of the classical solvers such as Newton-type methods are highly sensitive to the initial guess of the solution. However, it is very difficult to select good initial solutions for most systems of nonlinear equations. By including the global search capabilities of chaos optimization and the high local convergence rate of quasi-Newton method, a hybrid approach for solving systems of nonlinear equations is proposed. Three systems of nonlinear equations including the “Combustion of Propane” problem are used to test our proposed approach. The results show that the hybrid approach has a high success rate and a quick convergence rate. Besides, the hybrid approach guarantees the location of solution with physical meaning, whereas the quasi-Newton method alone cannot achieve this.     

An Inexact Alternating Directions Algorithm for Constrained Total Variation Regularized Compressive Sensing Problems

Recently, the efficient solvers for compressive sensing (CS) problems with Total Variation (TV) regularization are needed, mainly because of the reconstruction of an image by a single pixel camera, or the recovery of a medical image from its partial Fourier samples. In this paper, we propose an alternating directions scheme algorithm for solving the TV regularized minimization problems with linear constraints. We minimize the corresponding augmented Lagrangian function alternatively at each step. Both of the resulting subproblems admit explicit solutions by applying a linear-time shrinkage. The algorithm is easily performed, in which, only two matrix-vector multiplications and two fast Fourier transforms are involved at per-iteration. The global convergence of the proposed algorithm follows directly in this literature. Numerical comparisons with the sate-of-the-art method TVLA3 illustrate that the proposed method is effective and promising.     

The power of ants in solving Distributed Constraint Satisfaction Problems

Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for artificial intelligence and multi-agent systems. Also, Ant Colony Optimization (ACO) is an important evolutionary method for solving various optimization problems. This paper demonstrates the power of ants in solving DCSPs and describes a new approach for such a solution, showing how it differs from previous ACO-based DCSP solvers. The presented algorithm is designed to provide the special requirements that are important in the distributed form of Constraint Satisfaction Problem (CSP). The paper describes the important criteria for distributed CSP and then demonstrates how the presented algorithm stands out over similar DCSP solvers considering these criteria. Finally, the proposed approach is evaluated on random binary problems. The practical results show that this method, in most of the cases, outperforms the Asynchronous Backtracking Algorithm (ABT) and Distributed Breakout Algorithm (DBA) two important algorithms in this field of research.     

Adaptive multigrid for finite element computations in plasticity

The solution of the system of equilibrium equations is the most time-consuming part in large-scale finite element computations of plasticity problems. The development of efficient solution methods are therefore of utmost importance to the field of computational plasticity. Traditionally, direct solvers have most frequently been used. However, recent developments of iterative solvers and preconditioners may impose a change. In particular, preconditioning by the multigrid technique is especially favorable in FE applications.The multigrid preconditioner uses a number of nested grid levels to improve the convergence of the iterative solver. Prolongation of fine-grid residual forces is done to coarser grids and computed corrections are interpolated to the fine grid such that the fine-grid solution successively is improved. By this technique, large 3D problems, invincible for solvers based on direct methods, can be solved in acceptable time at low memory requirements. By means of a posteriori error estimates the computational grid could successively be refined (adapted) until the solution fulfils a predefined accuracy level. In contrast to procedures where the preceding grids are erased, the previously generated grids are used in the multigrid algorithm to speed up the solution process.The paper presents results using the adaptive multigrid procedure to plasticity problems. In particular, different error indicators are tested.     

A parsimony tree for the SAT2002 competition

Twenty of the programs (solvers) submitted to the SAT 2002 Contest had no disqualifying errors. These solvers were run on 2023 satisfiability problems of varying hardnesses. Each solver was judged by which problems it could solve within the allowed time limit. Twelve solvers were best on some problem — they could solve it and the others could not. Only two solvers could not beat each remaining solver on some problems (where the problems could vary depending on which solver it was trying to beat). Thus, there is evidence that 18 solvers were extremely good. It is interesting to analyze the contest results in a way that groups together solvers with similar strengths and weaknesses. This paper uses the parsimony algorithm to produce a classification of the twenty solvers. The paper also has a second classification, almost the same as the first, for the twenty solvers, updated versions of two solvers, and a fictitious state of the art solver. The contest problems came in three groups, Industrial, Hand Made, and Random. The Random group of problems was about three times as large as the other two together. The classification identifies four groups of solvers (plus a miscellaneous group): weak solvers, incomplete solvers which are very good at some satisfiable Random problems, complete solvers which are very good at most Random problems, and complete solvers which are very good at Industrial and Hand Made problems.     

Proportioning with second-order information for model predictive control

We propose an algorithm for the effective solution of quadratic programming (QP) problems arising from model predictive control (MPC). MPC is a modern multivariable control method which gives the solution for a QP problem at each sample instant. Our algorithm combines the active-set strategy with the proportioning test to decide when to leave the actual active set. For the minimization in the face, we use a direct solver implemented by the Cholesky factors updates. The performance of the algorithm is illustrated by numerical experiments, and the results are compared with the state-of-the-art solvers on benchmarks from MPC.     

A parsimony tree for the SAT2002 competition

Twenty of the programs (solvers) submitted to the SAT 2002 Contest had no disqualifying errors. These solvers were run on 2023 satisfiability problems of varying hardnesses. Each solver was judged by which problems it could solve within the allowed time limit. Twelve solvers were best on some problem – they could solve it and the others could not. Only two solvers could not beat each remaining solver on some problems (where the problems could vary depending on which solver it was trying to beat). Thus, there is evidence that 18 solvers were extremely good. It is interesting to analyze the contest results in a way that groups together solvers with similar strengths and weaknesses. This paper uses the parsimony algorithm to produce a classification of the twenty solvers. The paper also has a second classification, almost the same as the first, for the twenty solvers, updated versions of two solvers, and a fictitious state of the art solver. The contest problems came in three groups, Industrial, Hand Made, and Random. The Random group of problems was about three times as large as the other two together. The classification identifies four groups of solvers (plus a miscellaneous group): weak solvers, incomplete solvers which are very good at some satisfiable Random problems, complete solvers which are very good at most Random problems, and complete solvers which are very good at Industrial and Hand Made problems.     

Distributed generic approximate sparse inverses

The need for accuracy in the solution of linear systems derived from the discretization of partial differential equations leads to large sparse linear systems. The solution of sparse linear systems requires efficient scalable methods. Iterative solvers require efficient parallel preconditioning methods to solve effectively sparse linear systems. Herewith, a new parallel algorithm for the generic approximate sparse inverse matrix method for distributed memory systems is proposed. The computation of the distributed generic approximate sparse inverse matrix is based on a column-wise approach, which allows the separation to independent problems that can be handled in parallel without synchronization points or intermediate communications. This is achieved by reforming the generic approximate sparse inverse matrix algorithm and its process of computation with a new partial solution method for the computation of the nonzero elements of each column dictated by the approximate inverse sparsity pattern. Moreover, an algorithmic scheme is proposed for the efficient distribution of data amongst the available workstations, along with a load balancing scheme for problems with large standard deviation in the number of nonzero elements per column. Numerical results are presented for the proposed schemes for various model problems.