Search

Your search keyword '"Théo Mary"' showing total 9 results
Start Over Author "Théo Mary" Topic [info]computer science [cs]
9 results on '"Théo Mary"'

1. Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR^2 Format

Author

Alfredo Buttari, Théo Mary, Cleve Ashcraft, ANSYS, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées, Performance et Qualité des Algorithmes Numériques (PEQUAN), Laboratoire d'Informatique de Paris 6 (LIP6), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Centre National de la Recherche Scientifique (CNRS), and LIP6

Subjects
Rank (linear algebra), Astrophysics::High Energy Astrophysical Phenomena, 010103 numerical & computational mathematics, Astrophysics::Cosmology and Extragalactic Astrophysics, computer.software_genre, 01 natural sciences, law.invention, Separable space, Matrix (mathematics), law, numerical linear algebra, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Column (data store), Astrophysics::Galaxy Astrophysics, Mathematics, Block (data storage), Discrete mathematics, hierarchical matrices, Numerical linear algebra, block low-rank matrices, Special class, LU decomposition, Data sparse matrices, LU factorization, computer, Analysis, block separable matrices
Abstract

International audience; We investigate a special class of data sparse rank-structured matrices that combine a flat block low-rank (BLR) partitioning with the use of shared (called nested in the hierarchical case) bases. This format is to H 2 matrices what BLR is to H matrices: we therefore call it the BLR 2 matrix format. We present algorithms for the construction and LU factorization of BLR 2 matrices, and perform their cost analysis-both asymptotically and for a fixed problem size. With weak admissibility, BLR 2 matrices reduce to block separable matrices (the flat version of HBS/HSS). Our analysis and numerical experiments reveal some limitations of BLR 2 matrices with weak admissibility, which we propose to overcome with two approaches: strong admissibility, and the use of multiple shared bases per row and column.

Published
2020

2. Solving Block Low-Rank Linear Systems by LU Factorization is Numerically Stable

Author

Nicholas J. Higham, Théo Mary, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), and Sorbonne Université (SU)

Subjects
Rank (linear algebra), floating-point arithmetic, General Mathematics, 010103 numerical & computational mathematics, computer.software_genre, 01 natural sciences, Stability (probability), law.invention, Factorization, law, Applied mathematics, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Mathematics, Numerical linear algebra, Applied Mathematics, Linear system, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], LU decomposition, rounding error analysis, 010101 applied mathematics, Computational Mathematics, numerical stability, Block low-rank matrices, LU factorization, Round-off error, computer, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Numerical stability
Abstract

Block low-rank (BLR) matrices possess a blockwise low-rank property that can be exploited to reduce the complexity of numerical linear algebra algorithms. The impact of these low-rank approximations on the numerical stability of the algorithms in floating-point arithmetic has not previously been analysed. We present rounding error analysis for the solution of a linear system by LU factorization of BLR matrices. Assuming that a stable pivoting scheme is used, we prove backward stability: the relative backward error is bounded by a modest constant times $\varepsilon $, where the low-rank threshold $\varepsilon $ is the parameter controlling the accuracy of the blockwise low-rank approximations. In addition to this key result, our analysis offers three new insights into the numerical behaviour of BLR algorithms. First, we compare the use of a global or local low-rank threshold and find that a global one should be preferred. Second, we show that performing intermediate recompressions during the factorization can significantly reduce its cost without compromising numerical stability. Third, we consider different BLR factorization variants and determine the update–compress–factor variant to be the best. Tests on a wide range of matrices from various real-life applications show that the predictions from the analysis are realized in practice.

Published
2020
Full Text
View/download PDF

3. Stochastic Rounding and its Probabilistic Backward Error Analysis

Author

Nicholas J. Higham, Théo Mary, Michael P. Connolly, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), and Sorbonne Université (SU)

Subjects
Floating point, floating-point arithmetic, 010103 numerical & computational mathematics, computer.software_genre, 01 natural sciences, Error analysis, numerical linear algebra, stochastic rounding, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], probabilistic backward error analysis, Mathematics, Real number, Numerical linear algebra, Applied Mathematics, Rounding, stagnation, Probabilistic logic, TheoryofComputation_GENERAL, round to nearest, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], rounding error analysis, Computational Mathematics, computer, Algorithm, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; Stochastic rounding rounds a real number to the next larger or smaller floating-point number with probabilities 1 minus the relative distances to those numbers. It is gaining attention in deep learning because it can increase the success of low precision computations. We compare basic properties of stochastic rounding with those for round to nearest, finding properties in common as well as significant differences. We prove that for stochastic rounding the rounding errors are mean independent random variables with zero mean. We derive a new version of our probabilistic error analysis theorem from [SIAM J. Sci. Comput., 41 (2019), pp. A2815-A2835], weakening the assumption of independence of the random variables to mean independence. These results imply that for a wide range of linear algebra computations the backward error for stochastic rounding is unconditionally bounded by a multiple of √ nu to first order, with a certain probability, where n is the problem size and u is the unit roundoff. This is the first scenario where the rule of thumb that one can replace nu by √ nu in a rounding error bound has been shown to hold without any additional assumptions on the rounding errors. We also explain how stochastic rounding avoids the phenomenon of stagnation in sums, whereby small addends are obliterated by round to nearest when they are too small relative to the sum.

Published
2020
Full Text
View/download PDF

4. Sharper Probabilistic Backward Error Analysis for Basic Linear Algebra Kernels with Random Data

Author

Nicholas J. Higham, Théo Mary, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Centre National de la Recherche Scientifique (CNRS), Sorbonne Université (SU), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Basic linear algebra, Numerical linear algebra, Floating point, Applied Mathematics, Probabilistic logic, 010103 numerical & computational mathematics, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], computer.software_genre, 01 natural sciences, Matrix multiplication, Computational Mathematics, Error analysis, Applied mathematics, [INFO]Computer Science [cs], 0101 mathematics, Concentration inequality, [MATH]Mathematics [math], Martingale (probability theory), computer, ComputingMilieux_MISCELLANEOUS, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Mathematics
Abstract

Standard backward error analyses for numerical linear algebra algorithms provide worst-case bounds that can significantly overestimate the backward error. Our recent probabilistic error analysis, w...

Published
2020
Full Text
View/download PDF

5. Mixed Precision Block Fused Multiply-Add: Error Analysis and Application to GPU Tensor Cores

Author

Nicholas J. Higham, Srikara Pranesh, Florent Lopez, Pierre Blanchard, Théo Mary, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Centre National de la Recherche Scientifique (CNRS), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
fused multiply-add, Floating point, floating-point arithmetic, Carry (arithmetic), matrix multiplication, 010103 numerical & computational mathematics, 01 natural sciences, law.invention, Computational science, Matrix (mathematics), law, Tensor (intrinsic definition), [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], NVIDIA GPU, Mathematics, Block (data storage), Multiply–accumulate operation, Applied Mathematics, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], LU decomposition, Matrix multiplication, rounding error analysis, Computational Mathematics, tensor cores, LU factorization, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; Computing units that carry out a fused multiply-add (FMA) operation with matrix arguments, referred to as tensor units by some vendors, have great potential for use in scientific computing. However, these units are inherently mixed precision and existing rounding error analyses do not support them. We consider a mixed precision block FMA that generalizes both the usual scalar FMA and existing tensor units. We describe how to exploit such a block FMA in the numerical linear algebra kernels of matrix multiplication and LU factorization and give detailed rounding error analyses of both kernels. An important application is to GMRES-based iterative refinement with block FMAs, for which our analysis provides new insight. Our framework is applicable to the tensor core units in the NVIDIA Volta and Turing GPUs. For these we compare matrix multiplication and LU factorization with TC16 and TC32 forms of FMA, which differ in the precision used for the output of the tensor cores. Our experiments on an NVDIA V100 GPU confirm the predictions of the analysis that the TC32 variant is much more accurate than the TC16 one, and they show that the accuracy boost is obtained with almost no performance loss.

Published
2020
Full Text
View/download PDF

6. Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic

Author

Clément Pernet, Daniel S. Roche, Théo Mary, Claude-Pierre Jeannerod, Université de Lyon, École normale supérieure - Lyon (ENS Lyon), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), School of Mathematics [Manchester], University of Manchester [Manchester], Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), United States Naval Academy, École normale supérieure de Lyon (ENS de Lyon), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Rank (linear algebra), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Block (permutation group theory), 010103 numerical & computational mathematics, Fast matrix arithmetic, 01 natural sciences, Omega, law.invention, Matrix (mathematics), Factorization, AMS subject classifications 15A23, 65F05, law, Strassen algorithm, [INFO]Computer Science [cs], 0101 mathematics, Arithmetic, [MATH]Mathematics [math], Mathematics, 010102 general mathematics, block low-rank matrices, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], LU decomposition, linear algebra, Linear algebra, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; We consider the LU factorization of an $n\times n$ matrix $A$ represented as a block low-rank (BLR) matrix: most of its off-diagonal blocks are approximated by matrices of small rank $r$, which reduces the asymptotic complexity of computing the LU factorization of A down to $O(n^2r)$. In this article, our aim is to further reduce this complexity by exploiting fast matrix arithmetic, that is, the ability to multiply two $n\times n$ full-rank matrices together for $O(n^\omega)$ flops, where $\omega

Published
2019
Full Text
View/download PDF

7. Performance and Scalability of the Block Low-Rank Multifrontal Factorization on Multicore Architectures

Author

Théo Mary, Jean-Yves L'Excellent, Alfredo Buttari, Patrick R. Amestoy, Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT), Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
Multi-core processor, Rank (linear algebra), Computer science, Applied Mathematics, sparse linear algebra, 010103 numerical & computational mathematics, Parallel computing, Solver, 010502 geochemistry & geophysics, 01 natural sciences, Reduction (complexity), Factorization, Elliptic partial differential equation, multifrontal factorization, Scalability, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Block Low-Rank, multicore architectures, Software, 0105 earth and related environmental sciences, Block (data storage)
Abstract

International audience; Matrices coming from elliptic Partial Differential Equations have been shown to have a low-rank property which can be efficiently exploited in multifrontal solvers to provide a substantial reduction of their complexity. Among the possible low-rank formats, the Block Low-Rank format (BLR) is easy to use in a general purpose multifrontal solver and its potential compared to standard (full-rank) solvers has been demonstrated. Recently, new variants have been introduced and it was proved that they can further reduce the complexity but their performance has never been analyzed. In this paper, we present a multithreaded BLR factorization, and analyze its efficiency and scalability in shared-memory multicore environments. We identify the challenges posed by the use of BLR approximations in multifrontal solvers and put forward several algorithmic variants of the BLR factorization that overcome these challenges by improving its efficiency and scalability. We illustrate the performance analysis of the BLR multifrontal factorization with numerical experiments on a large set of problems coming from a variety of real-life applications.

Published
2019
Full Text
View/download PDF

8. On the Complexity of the Block Low-Rank Multifrontal Factorization

Author

Jean-Yves L'Excellent, Théo Mary, Alfredo Buttari, Patrick R. Amestoy, Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT), Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique - CNRS (FRANCE), Ecole Normale Supérieure de Lyon - ENS de Lyon (FRANCE), Institut National Polytechnique de Toulouse - INPT (FRANCE), Institut National de la Recherche en Informatique et en Automatique - INRIA (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Université Claude Bernard-Lyon I - UCBL (FRANCE), and Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)

Subjects
Rank (linear algebra), 65F05, Property (programming), 010103 numerical & computational mathematics, 010502 geochemistry & geophysics, 15A23, 01 natural sciences, 65Y20, Reduction (complexity), Factorization, multifrontal factorization, 65F50, [INFO]Computer Science [cs], Multifrontal factorization, 0101 mathematics, [MATH]Mathematics [math], 0105 earth and related environmental sciences, Mathematics, Block (data storage), 65N30, Applied Mathematics, Order (ring theory), sparse linear algebra, Sparse linear algebra, Solver, Algebra, Calcul parallèle, distribué et partagé, Block low-rank, Computational Mathematics, Elliptic partial differential equation, Block Low-Rank AMS subject classifications 15A06, Block Low-Rank
Abstract

International audience; Matrices coming from elliptic Partial Differential Equations have been shown to have a low-rank property: well defined off-diagonal blocks of their Schur complements can be approximated by low-rank products and this property can be efficiently exploited in multifrontal solvers to provide a substantial reduction of their complexity. Among the possible low-rank formats, the Block Low-Rank format (BLR) is easy to use in a general purpose multifrontal solver and has been shown to provide significant gains compared to full-rank on practical applications. However, unlike hierarchical formats, such as H and HSS, its theoretical complexity was unknown. In this paper, we extend the theoretical work done on hierarchical matrices in order to compute the theoretical complexity of the BLR multifrontal factorization. We then present several variants of the BLR multifrontal factorization, depending on the strategies used to perform the updates in the frontal matrices and on the constraints on how numerical pivoting is handled. We show how these variants can further reduce the complexity of the factorization. In the best case (3D, constant ranks), we obtain a complexity of the order of O(n^4/3). We provide an experimental study with numerical results to support our complexity bounds.

Published
2017
Full Text
View/download PDF

9. Large-scale 3D EM modeling with a Block Low-Rank multifrontal direct solver

Author

Théo Mary, Piyoosh Jaysaval, Patrick R. Amestoy, Jean-Yves L'Excellent, Sébastien de la Kethulle de Ryhove, Alfredo Buttari, Daniil V. Shantsev, emgs [Oslo], Department of Physics [Oslo], Faculty of Mathematics and Natural Sciences [Oslo], University of Oslo (UiO)-University of Oslo (UiO), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Université Toulouse III - Paul Sabatier (UT3), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - INPT (FRANCE), Institut National de la Recherche en Informatique et en Automatique - INRIA (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), University of Texas at Austin (USA), University of Oslo (NORWAY), Institut de Recherche en Informatique de Toulouse - IRIT (Toulouse, France), and Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)

Subjects
Floating point, Discretization, Rank (linear algebra), Computer science, 010103 numerical & computational mathematics, 010502 geochemistry & geophysics, 01 natural sciences, Numerical solutions, Matrix decomposition, Computational science, Factorization, Geochemistry and Petrology, Numerical approximations and analysis, [INFO]Computer Science [cs], 0101 mathematics, 0105 earth and related environmental sciences, Block (data storage), Linear system, Solver, Electromagnetic theory, Calcul parallèle, distribué et partagé, Geophysics, Numerical modelling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Marine electromagnetics, Controlled source electromagnetics (CSEM)
Abstract

International audience; We put forward the idea of using a Block Low-Rank (BLR) multifrontal direct solver to efficiently solve the linear systems of equations arising from a finite-difference discretization of the frequency-domain Maxwell equations for 3-D electromagnetic (EM) problems. The solver uses a low-rank representation for the off-diagonal blocks of the intermediate dense matrices arising in the multifrontal method to reduce the computational load. A numerical threshold, the so-called BLR threshold, controlling the accuracy of low-rank representations was optimized by balancing errors in the computed EM fields against savings in floating point operations (flops). Simulations were carried out over large-scale 3-D resistivity models representing typical scenarios for marine controlled-source EM surveys, and in particular the SEG SEAM model which contains an irregular salt body. The flop count, size of factor matrices and elapsed run time for matrix factorization are reduced dramatically by using BLR representations and can go down to, respectively, 10, 30 and 40 per cent of their full-rank values for our largest system with N = 20.6 million unknowns. The reductions are almost independent of the number of MPI tasks and threads at least up to 90 × 10 = 900 cores. The BLR savings increase for larger systems, which reduces the factorization flop complexity from O(N2) for the full-rank solver to O(Nm) with m = 1.4–1.6. The BLR savings are significantly larger for deep-water environments that exclude the highly resistive air layer from the computational domain. A study in a scenario where simulations are required at multiple source locations shows that the BLR solver can become competitive in comparison to iterative solvers as an engine for 3-D controlled-source electromagnetic Gauss–Newton inversion that requires forward modelling for a few thousand right-hand sides.

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results