Search

International audience; We describe an interpretation of parareal as a two-level additive Schwarz preconditioner in the time domain. We show that this twolevel preconditioner in time is equivalent to parareal and to multigrid reduction in time (MGRIT) with F-relaxation. We also discuss the case when additional fine or coarse propagation steps are applied in the preconditioner. This leads to procedures equivalent to MGRIT with FCF-relaxation and to MGRIT with F(CF) 2-relaxation or overlapping parareal. Numerical results show that these variants have faster convergence in some cases. In addition, we also apply a Krylov subspace method, namely GMRES (Generalized Minimal Residual), to accelerate the parareal algorithm. Better convergence is obtained, especially for the advection-reaction-diffusion equation in the case when advection and reaction coefficients are large.

International audience; This article presents deflation strategies related to recycling Krylov subspace methods for solving one or a sequence of linear systems of equations. Besides well-known strategies of deflation, Ritz-, and harmonic Ritz-based deflation, we introduce an Singular Value Decomposition based deflation technique. We consider the recycling in two contexts: recycling the Krylov subspace between the restart cycles and recycling a deflation subspace when the matrix changes in a sequence of linear systems. Numerical experiments on real-life reservoir simulation demonstrate the impact of our proposed strategy.

We are interested in parallelizing the Least Angle Regression (LARS) algorithm for fitting linear regression models to high-dimensional data. We consider two parallel and communication avoiding versions of the basic LARS algorithm. The two algorithms have different asymptotic costs and practical performance. One offers more speedup and the other produces more accurate output. The first is bLARS, a block version of LARS algorithm, where we update b columns at each iteration. Assuming that the data are row-partitioned, bLARS reduces the number of arithmetic operations, latency, and bandwidth by a factor of b. The second is Tournament-bLARS (T-bLARS), a tournament version of LARS where processors compete by running several LARS computations in parallel to choose b new columns to be added in the solution. Assuming that the data are column-partitioned, T-bLARS reduces latency by a factor of b. Similarly to LARS, our proposed methods generate a sequence of linear models. We present extensive numerical experiments that illustrate speedups up to 4x compared to LARS without any compromise in solution quality., Comment: 21 pages, 8 figures, 3 tables

International audience; This paper introduces an adaptive preconditioner for iterative solution of sparse linear systems arising from partial differential equations with self-adjoint operators. This preconditioner allows to control the growth rate of a dominant part of the algebraic error within a fixed point iteration scheme. Several numerical results that illustrate the efficiency of this adaptive preconditioner with a PCG solver are presented and the preconditioner is also compared with a previous variant in the literature.

Fast Multipole Methods (FMMs) based on the oscillatory Helmholtz kernel can reduce the cost of solving N-body problems arising from Boundary Integral Equations (BIEs) in acoustic or electromagnetics. However, their cost strongly increases in the high-frequency regime. This paper introduces a new directional FMM for oscillatory kernels (defmm - directional equispaced interpolation-based fmm), whose precomputation and application are FFT-accelerated due to polynomial interpolations on equispaced grids. We demonstrate the consistency of our FFT approach, and show how symmetries can be exploited in the Fourier domain. We also describe the algorithmic design of defmm, well-suited for the BIE non-uniform particle distributions, and present performance optimizations on one CPU core. Finally, we exhibit important performance gains on all test cases for defmm over a state-of-the-art FMM library for oscillatory kernels.

International audience; Krylov methods are widely used for solving large sparse linear systems of equations. On distributed architectures, their performance is limited by the communication needed at each iteration of the algorithm. In this paper, we study the use of so-called enlarged Krylov subspaces for reducing the number of iterations, and therefore the overall communication, of Krylov methods. In particular, we consider a reformulation of the conjugate gradient method using these enlarged Krylov subspaces: the enlarged conjugate gradient method. We present the parallel design of two variants of the enlarged conjugate gradient method, as well as their corresponding dynamic versions, where the number of search directions is dynamically reduced during the iterations. For a linear elasticity problem with heterogeneous coefficients, using a block Jacobi preconditioner, we show that this implementation scales up to 16,384 cores and is up to 6.9 times faster than the PETSc implementation of PCG.

International audience; In this paper we present a multilevel preconditioner based on overlapping Schwarz methods for symmetric positive definite (SPD) matrices. Robust two-level Schwarz preconditioners exist in the literature to guarantee fast convergence of Krylov methods. As long as the dimension of the coarse space is reasonable, that is, exact solvers can be used efficiently, two-level methods scale well on parallel architectures. However, the factorization of the coarse space matrix may become costly at scale. An alternative is then to use an iterative method on the second level, combined with an algebraic preconditioner, such as a one-level additive Schwarz preconditioner. Nevertheless, the condition number of the resulting preconditioned coarse space matrix may still be large. One of the difficulties of using more advanced methods, like algebraic multigrid or even two-level overlapping Schwarz methods, to solve the coarse problem is that the matrix does not arise from a partial differential equation (PDE) anymore. We introduce in this paper a robust multilevel additive Schwarz preconditioner where at each level the condition number is bounded, ensuring a fast convergence for each nested solver. Furthermore, our construction does not require any additional information than for building a two-level method, and may thus be seen as an algebraic extension.

International audience In this work a numerical method is proposed to compress a tensor by constructing a piece-wise tensor approximation. This is defined by partitioning a tensor into sub-tensors and by computing a low-rank tensor approximation (in a given format) in each sub-tensor. Neither the partition nor the ranks are fixed a priori, but, instead, are obtained in order to fulfill a prescribed accuracy and optimize, to some extent, the storage. The different steps of the method are detailed and some numerical experiments are proposed to assess its performances.

We propose a new strategy for solving by the parareal algorithm highly oscillatory ordinary differential equations which are characteristics of a six-dimensional Vlasov equation. For the coarse solvers we use reduced models, obtained from the two-scale asymptotic expansions in [4] . Such reduced models have a low computational cost since they are free of high oscillations. The parareal method allows to improve their accuracy in a few iterations through corrections by fine solvers of the full model. We demonstrate the accuracy and the efficiency of the strategy in numerical experiments of short time and long time simulations of charged particles submitted to a large magnetic field. In addition, the convergence of the parareal method is obtained uniformly with respect to the vanishing stiff parameter.

International audience; In this paper, we discuss a new adaptive approach for iterative solution of sparse linear systems arising from partial differential equations (PDEs) with self-adjoint operators. The idea is to use the a posteriori estimated local distribution of the algebraic error in order to steer and guide the solve process in such way that the algebraic error is reduced more efficiently in the consecutive iterations. We first explain the motivation behind the proposed procedure and show that it can be equivalently formulated as constructing a special combination of preconditioner and initial guess for the original system. We present several numerical experiments in order to identify when the adaptive procedure can be of practical use.

International audience; This article presents an adaptive approach for solving linear systems arising from self-adjoint partial differential equations (PDE) problems discretized by cell-centered finite volume method and stemming from single-phase flow simulations. This approach aims at reducing the algebraic error in targeted parts of the domain using a posteriori error estimates. Numerical results of a reservoir simulation example for heterogeneous porous media in two dimensions are discussed. Using the adaptive solve procedure, we obtain a significant gain in terms of the number of time steps and iterations compared to a standard solve.; Cet article présente une approche adaptative pour la résolution de systèmes linéaires qui découlent de problèmes d’équations aux dérivées partielles (EDP) avec opérateurs auto-adjoints discrétisés par la méthode des volumes finis centrés en cellules et issus de simulations d’écoulement mono-phasique. Cette approche vise à réduire l’erreur algébrique dans des parties ciblées du domaine à l’aide d’estimateurs d’erreur a posteriori. Des résultats numériques d’un exemple de simulation de réservoir en milieux poreux hétérogènes en deux dimensions sont présentés. En utilisant la procédure adaptative de résolution, nous obtenons un gain significatif en termes de nombre de pas de temps et d’itérations par rapport à une résolution classique.

International audience; In this paper, we propose a stabilized dimensional factorization (SDF) preconditioner for saddle point problems arising from the discretization of Navier-Stokes equations. The idea is based on regularization, block factorization and selective approximation. The spectral properties of the preconditioned matrix are analyzed in details. Based on the analysis, we prescribe a reasonable choice of the regularization matrix W in the preconditioner. By using the connection with the RDF preconditioner, we determine the relaxation parameter α for the problems discretized by uniform grids and stretched grids, respectively. Finally, numerical experiments on the finite element discretizations of both steady and unsteady incompressible flow problems show that the SDF preconditioner is more efficient and robust than the RDF preconditioner, which has been illustrated very competitive with some existing preconditioners.

International audience; In this paper we propose linear-time CUR approximation algorithms for admissible matrices obtained from the hierarchical form of Boundary Element matrices. We propose a new approach called geometric sampling to obtain indices of most significant rows and columns usinginformation from the domains where the problem is posed. Our strategy is tailored to Boundary Element Methods (BEM) since it uses directly and explicitly the cluster tree containing information from the problem geometry. Our CUR algorithm has precision comparable with low-rankapproximations created with the truncated QR factorization with column pivoting (QRCP) and the Adaptive Cross Approximation (ACA) with full pivoting, which are quadratic-cost methods. When compared to the well-known linear-time algorithm ACA with partial pivoting, we show that our algorithm improves, in general, the convergence error and overcomes some cases where ACA fails. We provide a general relative error bound for CUR approximations created with geometrical sampling. Finally, we evaluate the performance of our algorithms on traditional BEM problemsdefined over different geometries.; Dans cet article, nous présentons des algorithmes pour créer une approximation de rang faible de type CUR pour des matrices résultant de la discrétisation des équations intégrales par la méthode des éléments de frontière (BEM). Notre approche consiste à utiliser l’information sur la géométrie du problème pour choisir des colonnes et des lignes les plus représentatives de la matrice. Nous montrons que notre algorithme principal, dont le coût est linéaire, a la même précision que des méthodes, ayant coût quadratique, comme QRCP et Approximation Adaptative Croisée (ACA) avec pivotage complet. Nous présentons des expériences numériques sur des domaines complexes en utilisant des noyaux intégrales fréquemment utilisés dans la littérature.

We propose a variant of the generalized minimal residual (GMRES) method for solving linear systems of equations with one or multiple right-hand sides. Our method is based on the idea of the enlarged Krylov subspace to reduce communication. It can be interpreted as a block GMRES method. Hence, we are interested in detecting inexact breakdowns. We introduce a strategy to perform the test of detection. Furthermore, we propose a technique for deflating eigenvalues that has two benefits. The first advantage is to avoid the plateau of convergence after the end of a cycle in the restarted version. The second is to have very fast convergence when solving the same system with different right-hand sides, each given at a different time (useful in the context of a constrained pressure residual preconditioner). We test our method with these deflation techniques on academic test matrices arising from solving linear elasticity and convection–diffusion problems as well as matrices arising from two real-life applications, seismic imaging and simulations of reservoirs. With the same memory cost we obtain a saving of up to $50 \%$ in the number of iterations required to reach convergence with respect to the original method.

We discuss linear system solvers invoking a messenger-field and compare them with (preconditioned) conjugate gradient approaches. We show that the messenger-field techniques correspond to fixed point iterations of an appropriately preconditioned initial system of linear equations. We then argue that a conjugate gradient solver applied to the same preconditioned system, or equivalently a preconditioned conjugate gradient solver using the same preconditioner and applied to the original system, will in general ensure at least a comparable and typically better performance in terms of the number of iterations to convergence and time-to-solution. We illustrate our conclusions with two common examples drawn from the cosmic microwave background (CMB) data analysis: Wiener filtering and map-making. In addition, and contrary to the standard lore in the CMB field, we show that the performance of the preconditioned conjugate gradient solver can depend significantly on the starting vector. This observation seems of particular importance in the cases of map-making of high signal-to-noise ratio sky maps and therefore should be of relevance for the next generation of CMB experiments.

International audience; n this paper we present an algorithm for computing a low rank approximation of a sparse matrix based on a truncated LU factorization with column and row permutations. We present various approaches for determining the column and row permutations that show a trade-off between speed versus deterministic/probabilistic accuracy. We show that if the permutations are chosen by using tournament pivoting based on QR factorization, then the obtained truncated LU factorization with column/row tournament pivoting, LU_CRTP, satisfies bounds on the singular values which have similarities with the ones obtained by a communication avoiding rank revealing QR factorization. Experiments on challenging matrices show that LU_CRTP provides a good low rank approximation of the input matrix and it is less expensive than the rank revealing QR factorization in terms of computational and memory usage costs, while also minimizing the communication cost. We also compare the computational complexity of our algorithm with randomized algorithms and show that for sparse matrices and high enough but still modest accuracies, our approach is faster.

The efficient solution of block tridiagonal linear systems arising from the discretization of convection–diffusion problem is considered in this paper. Starting with the classical nested factorization, we propose a relaxed nested factorization preconditioner. Then, several combination preconditioners are developed based on relaxed nested factorization and a tangential filtering preconditioner. Influence of the relaxation parameter is numerically studied, the results indicate that the optimal relaxation parameter should be close to but less than 1. The number of iteration counts exhibit an extremely sensitive behaviour. This phenomena resembles the behaviour of relaxed ILU preconditioner. For symmetric positive-definite coefficient matrix, we also show that the proposed combination preconditioner is convergent. Finally, numerous test cases are carried out with both additive and multiplicative combinations to verify the robustness of the proposed preconditioners.

In this paper, we discuss the usage of overlapping techniques for improving the convergence of preconditioners based on incomplete factorizations. To enable parallelism, these preconditioners are usually applied after the input matrix is permuted into a nested arrow form using k-way nested dissection. This graph partitioning technique uses k-way partitionning by vertex separator to recursively partition the graph of the input matrix into k subgraphs using a subset of its vertices called a separator. The overlapping technique is then based on algebraically extending the associated subdomains of these subgraphs and their corresponding separators obtained from k-way nested dissection by their direct neighbours. A similar approach is known to accelerate the convergence of domain decomposition methods, where the input matrix is partitioned into a number of independent subdomains using k-way vertex partitioning of a graph by edge separators, a different graph decomposition technique. We discuss the effect of the overlapping technique on the convergence of two classes of preconditioners, on the basis of nested factorization and block incomplete LDU factorization.

This paper introduces a new preconditioning technique that is suitable for matrices arising from the discretization of a system of PDEs on unstructured grids. The preconditioner satisfies a so-called filtering property, which ensures that the input matrix is identical with the preconditioner on a given filtering vector. This vector is chosen to alleviate the effect of low-frequency modes on convergence and so decrease or eliminate the plateau that is often observed in the convergence of iterative methods. In particular, the paper presents a general approach that allows to ensure that the filtering condition is satisfied in a matrix decomposition. The input matrix can have an arbitrary sparse structure. Hence, it can be reordered using nested dissection, to allow a parallel computation of the preconditioner and of the iterative process. We show the efficiency of our preconditioner through a set of numerical experiments on symmetric and nonsymmetric matrices.

In this paper we study a class of preconditioners that satisfy the so-called left and/or right filtering conditions. For practical applications, we use a multiplicative combination of filtering based preconditioners with the classical ILU(0) preconditioner, which is known to be efficient. Although the left filtering condition has a more sound theoretical motivation than the right one, extensive tests on convection–diffusion equations with heterogeneous and anisotropic diffusion tensors reveal that satisfying left or right filtering conditions lead to comparable results. On the filtering vector, these numerical tests reveal that e=[1,…,1]T is a reasonable choice, which is effective and can avoid the preprocessing needed in other methods to build the filtering vector. Numerical tests show that the composite preconditioners are rather robust and efficient for these problems with strongly varying coefficients.

The shift-and-invert method is very efficient in eigenvalue computations, in particular when interior eigenvalues are sought. This method involves solving linear systems of the form ([email protected])z=b. The shift @s is variable, hence when a direct method is used to solve the linear system, the LU factorization of ([email protected]) needs to be computed for every shift change. We present two strategies that reduce the number of floating point operations performed in the LU factorization when the shift changes. Both methods perform first a preprocessing step that aims at eliminating parts of the matrix that are not affected by the diagonal change. This leads to about 43% and 50% flops savings respectively for the dense matrices.

In this paper, a modified tangential frequency filtering decomposition (MTFFD) preconditioner is proposed. The optimal order of the modification and the optimal relaxation parameter is determined by Fourier analysis. With the choice of optimal order of modification, the Fourier results show that the condition number of the preconditioned matrix is $${{\mathcal O}(h^{-\frac{2}{3}})}$$, and the spectrum distribution of the preconditioned matrix can be predicted by the Fourier results. The performance of MTFFD preconditioner is compared with tangential frequency filtering (TFFD) preconditioner on a variety of large sparse matrices arising from the discretization of PDEs with discontinuous coefficients. The numerical results show that the MTFFD preconditioner is much more efficient than the TFFD preconditioner.

In this paper we discuss a hypergraph-based unsymmetric nested dissection (HUND) ordering for reducing the fill-in incurred during Gaussian elimination. It has several important properties. It takes a global perspective of the entire matrix, as opposed to local heuristics. It takes into account the asymmetry of the input matrix by using a hypergraph to represent its structure. It is suitable for performing Gaussian elimination in parallel, with partial pivoting. This is possible because the row permutations performed due to partial pivoting do not destroy the column separators identified by the nested dissection approach. The hypergraph nested dissection approach is essentially equivalent to graph nested dissection on the matrix $A^{T}A$, but we need only the original matrix $A$ and never form the usually denser matrix $A^{T}A$. The usage of hypergraphs in our approach is fairly standard, and HUND can be implemented by calling an existing hypergraph partitioner that uses recursive bisection. Our implementation uses local reordering constrained column approximate minimum degree (CCOLAMD) to further improve the ordering. We also explain how weighted matching (HSL routine MC64) can be used in this context. Experimental results on 27 medium and large size matrices with highly unsymmetric structures compare our approach to four other well-known reordering algorithms. The results show that it provides a robust reordering algorithm, in the sense that it is the best or close to the best (often within 10%) of all the other methods, in particular on matrices with highly unsymmetric structures.

We consider the iterative solution of the linear systems arising from four convection-diffusion model problems: the scalar convection-diffusion problem, Stokes problem, Oseen problem, and Navier-Stokes problem. We give the explicit Kronecker product structure of the coefficient matrices, especially the Kronecker product structure for the convection term. For the latter three model cases, the coefficient matrices have a $2 \times 2$ blocks, and each block is a Kronecker product or a summation of several Kronecker products. We use the Kronecker products and block structures to design the diagonal block preconditioner, the tridiagonal block preconditioner and the constraint preconditioner. We can find that the constraint preconditioner can be regarded as the modification of the tridiagonal block preconditioner and the diagonal block preconditioner based on the cell Reynolds number. That's the reason why the constraint preconditioner is usually better. We also give numerical examples to show the efficiency of this kind of Kronecker product approximation preconditioners.

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property.

This paper presents the design and implementation of a memory scalable parallel symbolic factorization algorithm for general sparse unsymmetric matrices. Our parallel algorithm uses a graph partitioning approach, applied to the graph of $|A|+|A|^T$, to partition the matrix in such a way that is good for sparsity preservation as well as for parallel factorization. The partitioning yields a so-called separator tree which represents the dependencies among the computations. We use the separator tree to distribute the input matrix over the processors using a block cyclic approach and a subtree to subprocessor mapping. The parallel algorithm performs a bottom-up traversal of the separator tree. With a combination of right-looking and left-looking partial factorizations, the algorithm obtains one column structure of $L$ and one row structure of $U$ at each step. The algorithm is implemented in C and MPI. From a performance study on large matrices, we show that the parallel algorithm significantly reduces the memory requirement of the symbolic factorization step, as well as the overall memory requirement of the parallel solver. It also often reduces the runtime of the sequential algorithm, which is already relatively small. In general, the parallel algorithm prevents the symbolic factorization step from being a time or memory bottleneck of the parallel solver.

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.

In this paper we present the concept of affine low-rank approximation for an $$m\times n$$ matrix, consisting in fitting its columns into an affine subspace of dimension at most $$k \ll \min (m,n)$$ . We present the algorithm ALORA that constructs an affine approximation by slightly modifying the application of any low-rank approximation method. We focus on approximations created with the classical QRCP and subspace iteration algorithms. For the former, we discuss existing pivoting techniques and provide a bound for the error when an arbitrary pivoting technique is used. For the case of fsubspace iteration, we prove a result on the convergence of singular vectors, showing a bound that agrees with the one recently proved for the convergence of singular values. Finally, we present numerical experiments using challenging matrices taken from different fields, showing good performance and validating the theoretical framework.