Projection methods in flexible multibody dynamics. Part I: Kinematics

In this paper a recursive projection method for the dynamic analysis of open-loop mechanical systems that consist of a set of interconnected deformable bodies is presented. The configuration of each body in the system is identified using a coupled set of reference and elastic co-ordinates. The absolute velocities and accelerations of leaf or child bodies in the open-loop system are expressed in terms of the absolute velocities and accelerations of the parent bodies and the time derivatives of the relative co-ordinates of the joints between the bodies. The dynamic differential equations of motion are developed for each link using the generalized Newton-Euler equations. The relationship between the actual joint reactions and the generalized forces combined with the kinematic relationships and the generalized Newton-Euler equations are used to develop a system of loosely coupled equations which has a sparse matrix structure. Using matrix partitioning and recursive projection techniques based on optimal block factorization an efficient solution for the system accelerations and joint reaction forces is obtained. This solution technique yields a much smaller operations count and can more effectively exploit vectorization and parallel processing. It also allows a systematic procedure for decoupling the joint and elastic accelerations.     

A parallel row-oriented sparse solution method for finite element structural analysis

This paper describes a parallel implementation of LDL^T factorization on a distributed-memory parallel computer. Specifically, the parallel LDL^T factorization procedure is based on a row-oriented sparse storage scheme. In addition, a strategy is proposed for the parallel solution of a triangular system of equations. The strategy is to compute the inverses of the dense principal diagonal block submatrices of the factor L, stored in a row-oriented structure. Experimental results for a number of finite element models are presented to illustrate the effectiveness of the parallel solution schemes.     

A comparison of direct and preconditioned iterative techniques for sparse,unsymmetric systems of linear equations

In this paper we compare direct and preconditioned iterative methods for the solution of nonsymmetric, sparse systems of linear algebraic equations. These problems occur in finite difference and finite element simulations of semiconductor devices, and fluid flow problems. We consider five iterative methods that appear to be the most promising for this class of problems: the biconjugate gradient method, the conjugate gradient squared method, the generalized minimal residual method, the generalized conjugate residual method and the method of orthogonal minimization. Each of these methods was tested using similar preconditioning (incomplete LU factorization) on a set of large, sparse matrices arising from finite element simulation of semiconductor devices. Results are shown where we compare the computation time and memory requirements for each of these methods against one another, as well as against a direct method that uses LU factorization to solve these problems. The results of our numerical experiments show that preconditioned iterative methods are a practical alternative to direct methods in the solution of large, sparse systems of equations, and can offer significant savings in storage and CPU time.     

On sparse matrix orderings in interior point methods

The major computational task of most interior point implementations is solving systems of equations with symmetric coefficient matrix by direct factorization methods, therefore, the performance of Cholesky-like factorizations is a critical issue. In the case of sparse and large problems the efficiency of the factorizations is closely related to the exploitation of the nonzero structure of the problem. A number of techniques were developed for fill-reducing sparse matrix orderings which make Cholesky factorizations more efficient by reducing the necessary floating point computations. We present a variant of the nested dissection algorithm incorporating special techniques that are beneficial for graph partitioning problems arising in the ordering step of interior point implementations. We illustrate the behavior of our algorithm and provide numerical results and comparisons with other sparse matrix ordering algorithms.     

On modified incomplete cholesky factorization methods for the solution of problems with mixed boundary conditions and problems with discontinuous material conefficients

In Reference 1 a class of first-order factorization methods for the solution of large, sparse systems of equations, of which the coefficient matrix is a symmetric M-matrix, was introduced. Asymptotic results for the computational complexity was proved in the case of systems arising from finite difference approximation of second-order self-adjoint elliptic partial differential equation problems in two dimensions with Dirichlet boundary conditions. In this paper the result is extended to cover even mixed boundary conditions and problems with discontinuous material coefficients. Results from numerical experiments with various finite difference and finite element approximations are presented and comparisons with direct and other interative methods are made.     

Numerical solution of a parabolic system with coupled nonlinear boundary conditions

A numerical technique has been developed to solve a system that consists of m linear parabolic differential equations with coupled nonlinear boundary conditions. Such a system may represent chemical reactions, chemical lasers and diffusion problems. An implicit finite difference scheme is adopted to discretize the problem, and the resulting system of equations is solved by a novel technique that is a modification of the cyclic odd–even reduction and factorization (CORF) algorithm. At each time level, the system of equations is first reduced to m nonlinear algebraic equations that involve only the m unknown grid points on the nonlinear boundary. Newton's method is used to determine these m unknowns, and the corresponding Jacobian matrix can be computed and updated easily. After convergence is achieved, the remaining unknowns are solved directly. The efficiency of this technique is illustrated by the numerical computations of two examples previously solved by the cubic spline Galerkin method.     

Towards an accurate performance modeling of parallel sparse factorization

We present a simulation-based performance model to analyze a parallel sparse LU factorization algorithm on modern cached-based, high-end parallel architectures. We consider supernodal right-looking parallel factorization on a bi-dimensional grid of processors, that uses static pivoting. Our model characterizes the algorithmic behavior by taking into account the underlying processor speed, memory system performance, as well as the interconnect speed. The model is validated using the implementation in the SuperLU_DIST linear system solver, the sparse matrices from real application, and an IBM POWER3 parallel machine. Our modeling methodology can be adapted to study performance of other types of sparse factorizations, such as Cholesky or QR, and on different parallel machines.     

Sparse matrix factor modification in structural reanalysis

Structural reanalysis problems, such as in nonlinear finite element analysis or optimum design, involve progressive changes in the global stiffness matrix and its matrix factors. Although many studies have been devoted to the subject of matrix factor modification, most investigations have dealt with the problem separately from sparse matrix methods. This paper introduces a graph-theoretic model for the forward solution procedure which is applicable for identifying the modified entries of the matrix factors due to changes in the original matrix. Applications of this graph-theoretic model to existing refactorization methods are presented. The relation between substructuring and sparse matrix ordering strategies, and their effects on reanalysis are discussed. Modification of a sparse matrix associated with an n × n finite element grid ordered by the nested dissection scheme is analysed.     

A fast,memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices

In this article, we introduce a fast, memory efficient and robust sparse preconditioner that is based on a direct factorization scheme for sparse matrices arising from the finite‐element discretization of elliptic partial differential equations. We use a fast (but approximate) multifrontal approach as a preconditioner and use an iterative scheme to achieve a desired accuracy. This approach combines the advantages of direct and iterative schemes to arrive at a fast, robust, and accurate preconditioner. We will show that this approach is faster (～2×) and more memory efficient (～2–3×) than a conventional direct multifrontal approach. Furthermore, we will demonstrate that this preconditioner is both faster and more effective than other preconditioners such as the incomplete LU preconditioner. Specific speedups depend on the matrix size and improve as the size of the matrix increases. The preconditioner can be applied to both structured and unstructured meshes in a similar manner. We build on our previous work and utilize the fact that dense frontal and update matrices, in the multifrontal algorithm, can be represented as hierarchically off‐diagonal low‐rank matrices. Using this idea, we replace all large dense matrix operations in the multifrontal elimination process with O(N) hierarchically off‐diagonal low‐rank operations to arrive at a faster and more memory efficient factorization scheme. We then use this direct factorization method at low accuracies as a preconditioner and apply it to various real‐life engineering test cases. Copyright © 2016 John Wiley & Sons, Ltd.     

On computational procedures for the force method

It is known that the matrix force method has certain advantages over the displacement method for a class of structural problems. It is also known that the force method, when carried out by the conventional Gauss-Jordan procedure, tends to fill in the problem data, making the method unattractive for large size, sparse problems. This poor fill-in property, however, is not necessarily inherent to the method, and the sparsity may be maintained if one uses what we call the Turn-Back LU Procedure. The purpose of this paper is two-fold. First, it is shown that there exist some close relationships between the force method and the least squares problem, and that many existing algebraic procedures to perform the force method can be regarded as applications/extensions of certain well-known matrix factorization schemes for the least squares problem. Secondly, it is demonstrated that these algebraic procedures for the force method can be unified form the matrix factorization viewpoint. Included in this unification is the Turn-Back LU Procedure, which was originally proposed by Topçu in his thesis.⁸ It is explained why this procedure tends to produce sparse and banded ‘self-stress’ and flexibility matrices with small band width. Some computational results are presented to demonstrate the superiority of the Turn-Back LU Procedure over the other schemes considered in this paper.     

An evaluation of limited‐memory sparse linear solvers for thermo‐mechanical applications

We consider the performance of sparse linear solvers for problems that arise from thermo‐mechanical applications. Such problems have been solved using sparse direct schemes that enable robust solution at the expense of memory requirements that grow non‐linearly with the dimension of the coefficient matrix. In this paper, we consider a class of preconditioned iterative solvers as a limited‐memory alternative to direct solution schemes. However, such preconditioned iterative solvers typically exhibit complex trade‐offs between reliability and performance. We therefore characterize such trade‐offs for systems from thermo‐mechanical problems by considering several preconditioning schemes including multilevel methods and those based on sparse approximate inversion and incomplete matrix factorization. We provide an analysis of computational costs and memory requirements for model thermo‐mechanical problems, indicating that certain incomplete factorization schemes can achieve good performance. We also provide empirical evaluations that corroborate our analysis and indicate the relative effectiveness of different solution schemes. Our results indicate that our drop‐threshold incomplete Cholesky preconditioning is more robust, efficient and flexible than other popular preconditioning schemes. In addition, we propose preconditioner reuse to amortize preconditioner construction cost over a sequence of linear systems that arise from non‐linear solutions in a plastic regime. Copyright © 2007 John Wiley & Sons, Ltd.     

On the general solution by a direct method of a large-scale singular system of linear equations: application to the analysis of floating structures

Finding the general solution of a singular system of linear equations requires computing a particular solution and a basis of the null space of the corresponding singular matrix. In this paper, we consider the case where the singular matrix is large and sparse, and the application calls for a direct solution method. We highlight the dependence of straightforward factorization algorithms on an arbitrary constant that can influence the correctness of the computed solution, and describe a family of improved direct solution methods that alleviate this problem. For structural mechanics applications, we propose a hybrid geometric–algebraic method that is more robust than the purely algebraic direct methods that are currently used for solving singular sparse systems of equations. We illustrate the potential of our proposed solution algorithms with examples from structural mechanics and domain-decomposition-based iterative solvers. © 1998 John Wiley & Sons, Ltd.     

Sparse hierarchical solvers with guaranteed convergence

Solving sparse linear systems from discretized partial differential equations is challenging. Direct solvers have, in many cases, quadratic complexity (depending on geometry), while iterative solvers require problem dependent preconditioners to be robust and efficient. Approximate factorization preconditioners such as incomplete LU factorization provide cheap approximations to the system matrix. However, even a highly accurate preconditioner may have deteriorating performance when the condition number of the system matrix increases. By increasing the accuracy on low-frequency errors, we propose a novel hierarchical solver with improved robustness with respect to the condition number of the linear system. This solver retains the linear computational cost and memory footprint of the original algorithm.     

Nonlinear thermal analysis with a boundary element zone condensation technique

This paper presents a substantially more economical technique for the boundary element analysis (BEA) of a large class of nonlinear heat transfer problems including those with temperature dependent conductivity, temperature dependent convection coefficients, and radiation boundary conditions. The technique involves an exact static condensation of boundary element zones in a multi-zone boundary element model. The condensed boundary element zone contributions to be overall sparse blocked boundary element system matrices are formed once in the first step of the iterative nonlinear solution process and subsequently reused as the nonlinear parts of the overall problem are evolved to a convergent solution. Through a series of example problems it is demonstrated that the zone condensation technique facilitates the use of highly convergent iterative strategies for the solution of the nonlinear heat transfer problem involving modification and subsequent factorization of the overall boundary element system left had side matrix. For heat transfer problems with localized nonlinear effects, the condensation technique is shown to allow for the solution of nonlinear problems in less than half the CPU time required by methods that do not employ condensation.     

An efficient high-precision recursive dynamic algorithm for closed-loop multibody systems

As most closed-loop multibody systems do not have independent generalized coordinates, their dynamic equations are differential/algebraic equations (DAEs). In order to accurately solve DAEs, a usual method is using generalized α-class numerical methods to convert DAEs into difference equations by differential discretization and solve them by the Newton iteration method. However, the complexity of this method is O(n²) or more in each iteration, since it requires calculating the complex Jacobian matrix. Therefore, how to improve computational efficiency is an urgent problem. In this paper, we modify this method to make it more efficient. The first change is in the phase of building dynamic equations. We use the spatial vector note and the recursive method to establish dynamic equations (DAEs) of closed-loop multibody systems, which makes the Jacobian matrix have a special sparse structure. The second change is in the phase of solving difference equations. On the basis of the topology information of the system, we simplify this Jacobian matrix by proper matrix processing and solve the difference equations recursively. After these changes, the algorithm complexity can reach O(n) in each iteration. The algorithm proposed in this paper is not only accurate, which can control well the position/velocity constraint errors, but also efficient. It is suitable for chain systems, tree systems, and closed-loop systems.     

Using domain decomposition to solve symmetric,positive-definite systems on the hypercube computer

A distributed method of solving sparse, positive-definite systems of equations, like those arising from many finite-element problems, on a hypercube computer is studied. A domain-decomposition method is introduced wherein the domain of the problem to be solved is physically split into several subdomains. Each of these subdomains is then distributed to a separate processor on the hypercube where the fill, factorization and solution of the system of equations proceeds. This physical split is based on a nodal ordering known as one-way dissection.⁴ The method is applied to two-dimensional electrostatic problems which are governed by Laplace's equation. Since the finite-element method is used to discretize the problem, the algorithm is developed to take full advantage of the inherent sparsity in the system of equations by using an envelope storage scheme. The method is applied to several geometries, and results as well as performance data for the algorithm will be given.     

A multidomain boundary element method for two equation turbulence models

The paper deals with the multidomain Boundary Element Method (BEM) for modelling 2D complex turbulent flow using low Reynolds two equation turbulence models. While the BEM is widely accepted for laminar flow this is the first case, where this method is applied for a complex flow problems using k–ε turbulence model. The integral boundary domain equations are discretised using mixed boundary elements and a multidomain method also known as subdomain technique. The resulting system matrix is overdetermined, sparse, block banded and solved using fast iterative linear least squares solver. The simulation of turbulent flow over a backward step is in excellent agreement with the finite volume method using the same turbulent model.     

An efficient out‐of‐core multifrontal solver for large‐scale unsymmetric element problems

In many applications where the efficient solution of large sparse linear systems of equations is required, a direct method is frequently the method of choice. Unfortunately, direct methods have a potentially severe limitation: as the problem size grows, the memory needed generally increases rapidly. However, the in‐core memory requirements can be limited by storing the matrix and its factors externally, allowing the solver to be used for very large problems. We have designed a new out‐of‐core package for the large sparse unsymmetric systems that arise from finite‐element problems. The code, which is called HSL _MA78 , implements a multifrontal algorithm and achieves efficiency through the use of specially designed code for handling the input/output operations and efficient dense linear algebra kernels. These kernels, which are available as a separate package called HSL _MA74 , use high‐level BLAS to perform the partial factorization of the frontal matrices and offer both threshold partial and rook pivoting. In this paper, we describe the design of HSL _MA78 and explain its user interface and the options it offers. We also describe the algorithms used by HSL _MA74 and illustrate the performance of our new codes using problems from a range of practical applications. Copyright © 2008 John Wiley & Sons, Ltd.     

Algorithms for construction of preconditioners based on incomplete block-factorizations of the matrix

When applying an incomplete block-factorization technique one needs sparse approximate inverses of the successive Schur complements computed throughout the factorization. Here we propose a method for the construction of such sparse approximate inverses. The method has an advantage over earlier versions, in that such approximate inverses of block-tridiagonal matrices can be computed in parallel. Comparative numerical experiments for solving a number of discretized diffusion equations by this preconditioning matrix in a preconditioned conjugate gradient method and earlier versions of incomplete block-factorization preconditioners are presented.     

Normalized explicit approximate inverse preconditioning for solving 3D boundary value problems on uniprocessor and distributed systems

Normalized explicit approximate inverse matrix techniques, based on normalized approximate factorization procedures, for solving sparse linear systems resulting from the finite difference discretization of partial differential equations in three space variables are introduced. Normalized explicit preconditioned conjugate gradient schemes in conjunction with normalized approximate inverse matrix techniques are presented for solving sparse linear systems. The convergence analysis with theoretical estimates on the rate of convergence and computational complexity of the normalized explicit preconditioned conjugate gradient method are also derived. A Parallel Normalized Explicit Preconditioned Conjugate Gradient method for distributed memory systems, using message passing interface (MPI) communication library, is also given along with theoretical estimates on speedups, efficiency and computational complexity. Application of the proposed method on a three‐dimensional boundary value problem is discussed and numerical results are given for uniprocessor and multicomputer systems. Copyright © 2005 John Wiley & Sons, Ltd.