Modeling and analysis of system reliability using phase‐type distribution closure properties

Phase‐type distribution closure properties are utilized to devise algorithms for generating reliability functions of systems with basic structures. These structures include series, parallel, K‐out‐of‐N, and standby structures with perfect/imperfect switch. The algorithms form a method for system reliability modeling and analysis based on the relationship between the system lifetime and component lifetimes for general structures. The proposed method is suitable for functional system reliability analysis, which can produce reliability functions of systems with independent components instead of only system reliability values. Once the system reliability function is obtained, other reliability measures such as the system's hazard function and mean time to failure can be obtained efficiently using only matrix algebra. Dimensional and numerical comparisons with computerized symbolic processing are also presented to show the superiority of the proposed method.     

On Finite Dimension Exchange Algorithms

Load balancing on parallel computers aims at equilibrating some initial load which is different from one processor to another. We consider only nearest neighbour algorithms: in each step a processor communicates only with its direct neighbours. Load balancing algorithms can be divided into two classes: diffusion and dimension exchange. Whereas the first is appropriate for the so‐called all‐port‐model where a processor can send tokens to all its neighbours at a time, the latter is useful for the one‐port‐model. Both kinds of algorithms can be viewed as methods for solving certain singular linear systems. Since a few years there exist finite diffusion algorithms which have the property that they compute l₂‐minimal flows. In this paper a new finite dimension exchange method will be presented that is based on edge‐colourings of the underlying graph. It is usually faster and more stable than its diffusion counterpart. The flows computed by the new method are not minimal but it can be shown that they are bounded. Our analysis is based on techniques from numerical linear algebra.     

Semiconvergence of parallel multisplitting methods for symmetric positive semidefinite linear systems

In this paper we construct some parallel relaxed multisplitting methods for solving consistent symmetric positive semidefinite linear systems, based on modified diagonally compensated reduction and incomplete factorizations. The semiconvergence of the parallel multisplitting method, relaxed multisplitting method and relaxed two‐stage multisplitting method are discussed. The results generalize some well‐known results for the nonsingular linear systems to the singular systems. Copyright © 2010 John Wiley & Sons, Ltd.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

Modulus‐based synchronous multisplitting iteration methods for linear complementarity problems

By an equivalent reformulation of the linear complementarity problem into a system of fixed‐point equations, we construct modulus‐based synchronous multisplitting iteration methods based on multiple splittings of the system matrix. These iteration methods are suitable to high‐speed parallel multiprocessor systems and include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, successive overrelaxation, and accelerated overrelaxation of the modulus type as special cases. We establish the convergence theory of these modulus‐based synchronous multisplitting iteration methods and their relaxed variants when the system matrix is an H ₊ ‐matrix. Numerical results show that these new iteration methods can achieve high parallel computational efficiency in actual implementations. Copyright © 2012 John Wiley & Sons, Ltd.     

Projected subgradient algorithms on systems of equilibrium problems

The paper proposes two parallel and cyclic algorithms for solving systems of equilibrium problems in Hilbert spaces. The algorithms combine two methods including the diagonal subgradient method and the projection method with parallel or cyclic computations. The obtained results can be considered as improvements over several previously known methods for systems of equilibrium problems in computational steps. The algorithms have also allowed to reduce several assumptions imposed on bifunctions. The strongly convergent theorems are established under suitable conditions.     

SERK2v2: A new second‐order stabilized explicit Runge‐Kutta method for stiff problems

Traditionally, explicit numerical algorithms have not been used with stiff ordinary differential equations (ODEs) due to their stability. Implicit schemes are usually very expensive when used to solve systems of ODEs with very large dimension. Stabilized Runge‐Kutta methods (also called Runge–Kutta–Chebyshev methods) were proposed to try to avoid these difficulties. The Runge–Kutta methods are explicit methods with extended stability domains, usually along the negative real axis. They can easily be applied to large problem classes with low memory demand, they do not require algebra routines or the solution of large and complicated systems of nonlinear equations, and they are especially suited for discretizations using the method of lines of two and three dimensional parabolic partial differential equations. In Martín‐Vaquero and Janssen [Comput Phys Commun 180 (2009), 1802–1810], we showed that previous codes based on stabilized Runge–Kutta algorithms have some difficulties in solving problems with very large eigenvalues and we derived a new code, SERK2, based on sixth‐order polynomials. Here, we develop a new method based on second‐order polynomials with up to 250 stages and good stability properties. These methods are efficient numerical integrators of very stiff ODEs. Numerical experiments with both smooth and nonsmooth data support the efficiency and accuracy of the new algorithms when compared to other well‐known second‐order methods such as RKC and ROCK2. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

On some versions of the element agglomeration AMGe method

The present paper deals with element‐based algebraic multigrid (AMGe) methods that target linear systems of equations coming from finite element discretizations of elliptic partial differential equations. The individual element information (element matrices and element topology) is the main input to construct the AMG hierarchy. We study a number of variants of the spectral agglomerate AMGe method. The core of the algorithms relies on element agglomeration utilizing the element topology (built recursively from fine to coarse levels). The actual selection of the coarse degrees of freedom is based on solving a large number of local eigenvalue problems. Additionally, we investigate strategies for adaptive AMG as well as multigrid cycles that are more expensive than the V‐cycle utilizing simple interpolation matrices and nested conjugate gradient (CG)‐based recursive calls between the levels. The presented algorithms are illustrated with an extensive set of experiments based on a matlab implementation of the methods. Copyright © 2008 John Wiley & Sons, Ltd.     

Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.     

Algorithms for solving inverse geophysical problems on parallel computing systems

For solving inverse gravimetry problems, efficient stable parallel algorithms based on iterative gradient methods are proposed. For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, a parallel matrix sweep algorithm, a square root method, and a conjugate gradient method with preconditioner are proposed. The algorithms are implemented numerically on a parallel computing system of the Institute of Mathematics and Mechanics (PCS-IMM), NVIDIA graphics processors, and an Intel multi-core CPU with some new computing technologies. The parallel algorithms are incorporated into a system of remote computations entitled “Specialized Web-Portal for Solving Geophysical Problems on Multiprocessor Computers.” Some problems with “quasi-model” and real data are solved.     

Numerical recovery strategies for parallel resilient Krylov linear solvers

As the computational power of high‐performance computing systems continues to increase by using a huge number of cores or specialized processing units, high‐performance computing applications are increasingly prone to faults. In this paper, we present a new class of numerical fault tolerance algorithms to cope with node crashes in parallel distributed environments. This new resilient scheme is designed at application level and does not require extra resources, that is, computational unit or computing time, when no fault occurs. In the framework of iterative methods for the solution of sparse linear systems, we present numerical algorithms to extract relevant information from available data after a fault, assuming a separate mechanism ensures the fault detection. After data extraction, a well‐chosen part of missing data is regenerated through interpolation strategies to constitute meaningful inputs to restart the iterative scheme. We have developed these methods, referred to as interpolation–restart techniques, for Krylov subspace linear solvers. After a fault, lost entries of the current iterate computed by the solver are interpolated to define a new initial guess to restart the Krylov method. A well‐suited initial guess is computed by using the entries of the faulty iterate available on surviving nodes. We present two interpolation policies that preserve key numerical properties of well‐known linear solvers, namely, the monotonic decrease of the A‐norm of the error of the conjugate gradient or the residual norm decrease of generalized minimal residual algorithm for solving. The qualitative numerical behavior of the resulting scheme has been validated with sequential simulations, when the number of faults and the amount of data losses are varied. Finally, the computational costs associated with the recovery mechanism have been evaluated through parallel experiments. Copyright © 2016 John Wiley & Sons, Ltd.     

Modified parallel multisplitting iterative methods for non-Hermitian positive definite systems

In this paper we present three modified parallel multisplitting iterative methods for solving non-Hermitian positive definite systems Ax?=?b. The first is a direct generalization of the standard parallel multisplitting iterative method for solving this class of systems. The other two are the iterative methods obtained by optimizing the weighting matrices based on the sparsity of the coefficient matrix A. In our multisplitting there is only one that is required to be convergent (in a standard method all the splittings must be convergent), which not only decreases the difficulty of constructing the multisplitting of the coefficient matrix A, but also releases the constraints to the weighting matrices (unlike the standard methods, they are not necessarily be known or given in advance). We then prove the convergence and derive the convergent rates of the algorithms by making use of the standard quadratic optimization technique. Finally, our numerical computations indicate that the methods derived are feasible and efficient.     

Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

Block two-stage preconditioners

Linear systems of the form Ax = b, where the matrix A is symmetric and positive definite, often arise from the discretization of elliptic partial differential equations. A very successful method for solving these linear systems is the preconditioned conjugate gradient method. In this paper, we study parallel preconditioners for the conjugate gradient method based on the block two-stage iterative methods. Sufficient conditions for the validity of these preconditioners are given. Computational results of these preconditioned conjugate gradient methods on two parallel computing systems are presented.     

Parallel Newton Two-Stage Multisplitting Iterative Methods for Nonlinear Systems

Parallel Newton two-stage iterative methods to solve nonlinear systems are studied. These algorithms are based on both the multisplitting technique and the two-stage iterative methods. Convergence properties of these methods are studied when the Jacobian matrix is either monotone or an H-matrix. Furthermore, in order to illustrate the performance of the algorithms studied, computational results about these methods on a distributed memory multiprocessor are discussed.This revised version was published online in October 2005 with corrections to the Cover Date.     

Parallel coarse‐grid selection

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse‐grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse‐grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd.     

On a new family of high‐order iterative methods for the matrix pth root

The main goal of this paper is to approximate the principal pth root of a matrix by using a family of high‐order iterative methods. We analyse the semi‐local convergence and the speed of convergence of these methods. Concerning stability, it is well known that even the simplified Newton method is unstable. Despite it, we present stable versions of our family of algorithms. We test numerically the methods: we check the numerical robustness and stability by considering matrices that are close to be singular and badly conditioned. We find algorithms of the family with better numerical behavior than the Newton and the Halley methods. These two algorithms are basically the iterative methods proposed in the literature to solve this problem. Copyright © 2015 John Wiley & Sons, Ltd.     

Multilevel approaches for FSAI preconditioning

Factorized sparse approximate inverse (FSAI) preconditioners are robust algorithms for symmetric positive matrices, which are particularly attractive in a parallel computational environment because of their inherent and almost perfect scalability. Their parallel degree is even redundant with respect to the actual capabilities of the current computational architectures. In this work, we present two new approaches for FSAI preconditioners with the aim of improving the algorithm effectiveness by adding some sequentiality to the native formulation. The first one, denoted as block tridiagonal FSAI, is based on a block tridiagonal factorization strategy, whereas the second one, domain decomposition FSAI, is built by reordering the matrix graph according to a multilevel k‐way partitioning method followed by a bandwidth minimization algorithm. We test these preconditioners by solving a set of symmetric positive definite problems arising from different engineering applications. The results are evaluated in terms of performance, scalability, and robustness, showing that both strategies lead to faster convergent schemes regarding the number of iterations and total computational time in comparison with the native FSAI with no significant loss in the algorithmic parallel degree.