Showing 1–23 of 23 results for author: Kanschat, G

Smoothers with localized residual computations for geometric multigrid methods

Authors: Michał Wichrowski, Peter Munch, Martin Kronbichler, Guido Kanschat

Abstract: We improve the performance of multigrid solvers on many-core architectures with cache hierarchies by reorganizing operations in the smoothing step to minimize memory transfers. We focus on patch smoothers, which offer robust convergence rates with respect to the finite element degree for various equations, in the setting of multiplicative subspace correction for numerical efficiency. By combining… ▽ More We improve the performance of multigrid solvers on many-core architectures with cache hierarchies by reorganizing operations in the smoothing step to minimize memory transfers. We focus on patch smoothers, which offer robust convergence rates with respect to the finite element degree for various equations, in the setting of multiplicative subspace correction for numerical efficiency. By combining the computation of local residuals with local solvers, we increase the locality of the problem and thus reduce data transfers. The thread-parallel implementation of this algorithm is based on coloring, which contradicts cache efficiency. We improve data locality by rearranging the loop into batches so that more data can be reused. The organization of consecutive batches prioritizes data locality. △ Less

Submitted 2 July, 2024; originally announced July 2024.

An implementation of tensor product patch smoothers on GPU

Authors: Cu Cui, Paul Grosse-Bley, Guido Kanschat, Robert Strzodka

Abstract: We present a GPU implementation of vertex-patch smoothers for higher order finite element methods in two and three dimensions. Analysis shows that they are not memory bound with respect to GPU DRAM, but with respect to on-chip scratchpad memory. Multigrid operations are optimized through localization and reorganized local operations in on-chip memory, achieving minimal global data transfer and a c… ▽ More We present a GPU implementation of vertex-patch smoothers for higher order finite element methods in two and three dimensions. Analysis shows that they are not memory bound with respect to GPU DRAM, but with respect to on-chip scratchpad memory. Multigrid operations are optimized through localization and reorganized local operations in on-chip memory, achieving minimal global data transfer and a conflict free memory access pattern. Performance tests demonstrate that the optimized kernel is at least 2 times faster than the straightforward implementation for the Poisson problem, across various polynomial degrees in 2D and 3D, achieving up to 36% of the peak performance in both single and double precision on Nvidia A100 GPU. △ Less

Submitted 30 May, 2024; v1 submitted 29 May, 2024; originally announced May 2024.

MSC Class: 65N55; 65Y20

Multilevel Interior Penalty Methods on GPUs

Authors: Cu Cui, Guido Kanschat

Abstract: We present a matrix-free multigrid method for high-order discontinuous Galerkin (DG) finite element methods with GPU acceleration. A performance analysis is conducted, comparing various data and compute layouts. Smoother implementations are optimized through localization and fast diagonalization techniques. Leveraging conflict-free access patterns in shared memory, arithmetic throughput of up to 3… ▽ More We present a matrix-free multigrid method for high-order discontinuous Galerkin (DG) finite element methods with GPU acceleration. A performance analysis is conducted, comparing various data and compute layouts. Smoother implementations are optimized through localization and fast diagonalization techniques. Leveraging conflict-free access patterns in shared memory, arithmetic throughput of up to 39% of the peak performance on Nvidia A100 GPUs are achieved. Experimental results affirm the effectiveness of mixed-precision approaches and MPI parallelization in accelerating algorithms. Furthermore, an assessment of solver efficiency and robustness is provided across both two and three dimensions, with applications to Poisson problems. △ Less

Submitted 30 May, 2024; v1 submitted 29 May, 2024; originally announced May 2024.

MSC Class: 65N55; 65Y20

Monolithic two-level Schwarz preconditioner for Biot's consolidation model in two space dimensions

Authors: Stefan Meggendorfer, Guido Kanschat, Johannes Kraus

Abstract: This paper addresses the construction and analysis of a class of domain decomposition methods for the iterative solution of the quasi-static Biot problem in three-field formulation. The considered discrete model arises from time discretization by the implicit Euler method and space discretization by a family of strongly mass-conserving methods exploiting $H^{div}$-conforming approximations of the… ▽ More This paper addresses the construction and analysis of a class of domain decomposition methods for the iterative solution of the quasi-static Biot problem in three-field formulation. The considered discrete model arises from time discretization by the implicit Euler method and space discretization by a family of strongly mass-conserving methods exploiting $H^{div}$-conforming approximations of the solid displacement and fluid flux fields. For the resulting saddle-point problem, we construct monolithic overlapping domain decomposition (DD) methods whose analysis relies on a transformation into an equivalent symmetric positive definite system and on stable decompositions of the involved finite element spaces under proper problem-dependent norms. Numerical results on two-dimensional test problems are in accordance with the provided theoretical uniform convergence estimates for the two-level multiplicative Schwarz method. △ Less

Submitted 25 April, 2024; originally announced April 2024.

Comments: 33 pages

MSC Class: 65M12; 65M55; 65F10

Homogeneous multigrid for hybrid discretizations: application to HHO methods

Authors: Daniele A. Di Pietro, Zhaonan Dong, Guido Kanschat, Pierre Matalon, Andreas Rupp

Abstract: We prove the uniform convergence of the geometric multigrid V-cycle for hybrid high-order (HHO) and other discontinuous skeletal methods. Our results generalize previously established results for HDG methods, and our multigrid method uses standard smoothers and local solvers that are bounded, convergent, and consistent. We use a weak version of elliptic regularity in our proofs. Numerical experime… ▽ More We prove the uniform convergence of the geometric multigrid V-cycle for hybrid high-order (HHO) and other discontinuous skeletal methods. Our results generalize previously established results for HDG methods, and our multigrid method uses standard smoothers and local solvers that are bounded, convergent, and consistent. We use a weak version of elliptic regularity in our proofs. Numerical experiments confirm our theoretical results. △ Less

Submitted 10 April, 2024; v1 submitted 23 March, 2024; originally announced March 2024.

Ensemble Kalman Inversion for Image Guided Guide Wire Navigation in Vascular Systems

Authors: Matei Hanu, Jürgen Hesser, Guido Kanschat, Javier Moviglia, Claudia Schillings, Jan Stallkamp

Abstract: This paper addresses the challenging task of guide wire navigation in cardiovascular interventions, focusing on the parameter estimation of a guide wire system using Ensemble Kalman Inversion (EKI) with a subsampling technique. The EKI uses an ensemble of particles to estimate the unknown quantities. However since the data misfit has to be computed for each particle in each iteration, the EKI may… ▽ More This paper addresses the challenging task of guide wire navigation in cardiovascular interventions, focusing on the parameter estimation of a guide wire system using Ensemble Kalman Inversion (EKI) with a subsampling technique. The EKI uses an ensemble of particles to estimate the unknown quantities. However since the data misfit has to be computed for each particle in each iteration, the EKI may become computationally infeasible in the case of high-dimensional data, e.g. high-resolution images. This issue can been addressed by randomised algorithms that utilize only a random subset of the data in each iteration. We introduce and analyse a subsampling technique for the EKI, which is based on a continuous-time representation of stochastic gradient methods and apply it to on the parameter estimation of our guide wire system. Numerical experiments with real data from a simplified test setting demonstrate the potential of the method. △ Less

Submitted 11 December, 2023; originally announced December 2023.

MSC Class: 65N21; 90C56; 68W20; 60J25 ACM Class: J.3

Discrete tensor product BGG sequences: splines and finite elements

Authors: Francesca Bonizzoni, Kaibo Hu, Guido Kanschat, Duygu Sap

Abstract: In this paper, we provide a systematic discretization of the Bernstein-Gelfand-Gelfand (BGG) diagrams and complexes over cubical meshes of arbitrary dimension via the use of tensor-product structures of one-dimensional piecewise-polynomial spaces, such as spline and finite element spaces. We demonstrate the construction of the Hessian, the elasticity, and the divdiv complexes as examples for our c… ▽ More In this paper, we provide a systematic discretization of the Bernstein-Gelfand-Gelfand (BGG) diagrams and complexes over cubical meshes of arbitrary dimension via the use of tensor-product structures of one-dimensional piecewise-polynomial spaces, such as spline and finite element spaces. We demonstrate the construction of the Hessian, the elasticity, and the divdiv complexes as examples for our construction. △ Less

Submitted 30 December, 2023; v1 submitted 5 February, 2023; originally announced February 2023.

Homogeneous multigrid method for HDG applied to the Stokes equation

Authors: Peipei Lu, Wei Wang, Guido Kanschat, Andreas Rupp

Abstract: We propose a multigrid method to solve the linear system of equations arising from a hybrid discontinuous Galerkin (in particular, a single face hybridizable, a hybrid Raviart--Thomas, or a hybrid Brezzi--Douglas--Marini) discretization of a Stokes problem. Our analysis is centered around the augmented Lagrangian approach and we prove uniform convergence in this setting. Numerical experiments unde… ▽ More We propose a multigrid method to solve the linear system of equations arising from a hybrid discontinuous Galerkin (in particular, a single face hybridizable, a hybrid Raviart--Thomas, or a hybrid Brezzi--Douglas--Marini) discretization of a Stokes problem. Our analysis is centered around the augmented Lagrangian approach and we prove uniform convergence in this setting. Numerical experiments underline our analytical findings. △ Less

Submitted 31 January, 2023; originally announced February 2023.

MSC Class: 65F10; 65N30; 65N50

A Tensor-Product Finite Element Cochain Complex with Arbitrary Continuity

Authors: Francesca Bonizzoni, Guido Kanschat

Abstract: We develop tensor product finite element cochain complexes of arbitrary smoothness on Cartesian meshes of arbitrary dimension. The first step is the construction of a one-dimensional $C^m$-conforming finite element cochain complex based on a modified Hermite interpolation operator, which is proved to commute with the exterior derivative by means of a general commutation lemma. Adhering to a strict… ▽ More We develop tensor product finite element cochain complexes of arbitrary smoothness on Cartesian meshes of arbitrary dimension. The first step is the construction of a one-dimensional $C^m$-conforming finite element cochain complex based on a modified Hermite interpolation operator, which is proved to commute with the exterior derivative by means of a general commutation lemma. Adhering to a strict tensor product construction we then derive finite element complexes in higher dimensions. △ Less

Submitted 1 July, 2022; originally announced July 2022.

MSC Class: 65N30

Partial differential equations on hypergraphs and networks of surfaces: derivation and hybrid discretizations

Authors: Andreas Rupp, Markus Gahn, Guido Kanschat

Abstract: We introduce a general, analytical framework to express and to approximate partial differential equations (PDEs) numerically on graphs and networks of surfaces---generalized by the term hypergraphs. To this end, we consider PDEs on hypergraphs as singular limits of PDEs in networks of thin domains (such as fault planes, pipes, etc.), and we observe that (mixed) hybrid formulations offer useful too… ▽ More We introduce a general, analytical framework to express and to approximate partial differential equations (PDEs) numerically on graphs and networks of surfaces---generalized by the term hypergraphs. To this end, we consider PDEs on hypergraphs as singular limits of PDEs in networks of thin domains (such as fault planes, pipes, etc.), and we observe that (mixed) hybrid formulations offer useful tools to formulate such PDEs. Thus, our numerical framework is based on hybrid finite element methods (in particular, the class of hybrid discontinuous Galerkin methods). △ Less

Submitted 16 August, 2021; originally announced August 2021.

MSC Class: 65M60; 65N30; 68N30; 53Z99; 57N99

Analysis of injection operators in multigrid solvers for hybridized discontinuous Galerkin methods

Authors: Peipei Lu, Andreas Rupp, Guido Kanschat

Abstract: Uniform convergence of the geometric multigrid V-cycle is proven for HDG methods with a new set of assumptions on the injection operators from coarser to finer meshes. The scheme involves standard smoothers and local solvers which are bounded, convergent, and consistent. Elliptic regularity is used in the proofs. The new assumptions admit injection operators local to a single coarse grid cell. Exa… ▽ More Uniform convergence of the geometric multigrid V-cycle is proven for HDG methods with a new set of assumptions on the injection operators from coarser to finer meshes. The scheme involves standard smoothers and local solvers which are bounded, convergent, and consistent. Elliptic regularity is used in the proofs. The new assumptions admit injection operators local to a single coarse grid cell. Examples for admissible injection operators are given. The analysis applies to the hybridized local discontinuous Galerkin method, hybridized Raviart-Thomas, and hybridized Brezzi-Douglas-Marini mixed element methods. Numerical experiments are provided to confirm the theoretical results. △ Less

Submitted 31 March, 2021; originally announced April 2021.

Comments: arXiv admin note: text overlap with arXiv:2011.14018

MSC Class: 65F10; 65N30; 65N50

Homogeneous multigrid for embedded discontinuous Galerkin methods

Authors: Peipei Lu, Andreas Rupp, Guido Kanschat

Abstract: We introduce a homogeneous multigrid method in the sense that it uses the same embedded discontinuous Galerkin (EDG) discretization scheme for Poisson's equation on all levels. In particular, we use the injection operator developed in [LuRK2020] for HDG and prove optimal convergence of the method under the assumption of elliptic regularity. Numerical experiments underline our analytical findings. We introduce a homogeneous multigrid method in the sense that it uses the same embedded discontinuous Galerkin (EDG) discretization scheme for Poisson's equation on all levels. In particular, we use the injection operator developed in [LuRK2020] for HDG and prove optimal convergence of the method under the assumption of elliptic regularity. Numerical experiments underline our analytical findings. △ Less

Submitted 29 January, 2021; originally announced January 2021.

Comments: arXiv admin note: substantial text overlap with arXiv:2011.14018

MSC Class: 65F10; 65N30; 65N50

HMG -- Homogeneous multigrid for HDG

Authors: Peipei Lu, Andreas Rupp, Guido Kanschat

Abstract: We introduce a homogeneous multigrid method in the sense that it uses the same HDG discretization scheme for Poisson's equation on all levels. In particular, we construct a stable injection operator and prove optimal convergence of the method under the assumption of elliptic regularity. Numerical experiments underline our analytical findings. We introduce a homogeneous multigrid method in the sense that it uses the same HDG discretization scheme for Poisson's equation on all levels. In particular, we construct a stable injection operator and prove optimal convergence of the method under the assumption of elliptic regularity. Numerical experiments underline our analytical findings. △ Less

Submitted 27 November, 2020; originally announced November 2020.

MSC Class: 65F10; 65N30; 65N50

H1-conforming finite element cochain complexes and commuting quasi-interpolation operators on cartesian meshes

Authors: Francesca Bonizzoni, Guido Kanschat

Abstract: A finite element cochain complex on Cartesian meshes of any dimension based on the H1-inner product is introduced. It yields H1-conforming finite element spaces with exterior derivatives in H1. We use a tensor product construction to obtain L2-stable projectors into these spaces which commute with the exterior derivative. The finite element complex is generalized to a family of arbitrary order. A finite element cochain complex on Cartesian meshes of any dimension based on the H1-inner product is introduced. It yields H1-conforming finite element spaces with exterior derivatives in H1. We use a tensor product construction to obtain L2-stable projectors into these spaces which commute with the exterior derivative. The finite element complex is generalized to a family of arbitrary order. △ Less

Submitted 1 October, 2020; originally announced October 2020.

MSC Class: 65N30

Journal ref: Calcolo 58, 18 (2021)

Fast Tensor Product Schwarz Smoothers for High-Order Discontinuous Galerkin Methods

Authors: Julius Witte, Daniel Arndt, Guido Kanschat

Abstract: In this article, we discuss the efficient implementation of powerful domain decomposition smoothers for multigrid methods for high order discontinuous Galerkin (DG) finite element methods. In particular, we study the inversion of matrices associated to mesh cells and to the patches around a vertex, respectively, in order to obtain fast local solvers for additive and multiplicative subspace correct… ▽ More In this article, we discuss the efficient implementation of powerful domain decomposition smoothers for multigrid methods for high order discontinuous Galerkin (DG) finite element methods. In particular, we study the inversion of matrices associated to mesh cells and to the patches around a vertex, respectively, in order to obtain fast local solvers for additive and multiplicative subspace correction methods. The effort of inverting local matrices for tensor product polynomials of degree $k$ is reduced from $\mathcal O(k^{3d})$ to $\mathcal O(dk^{d+1})$ by exploiting the separability of the differential operator and resulting low rank representation of its inverse as a prototype for more general low rank representations. △ Less

Submitted 24 October, 2019; originally announced October 2019.

MSC Class: 65N55; 65Y20

A Flexible, Parallel, Adaptive Geometric Multigrid method for FEM

Authors: Thomas C. Clevenger, Timo Heister, Guido Kanschat, Martin Kronbichler

Abstract: We present the design and implementation details of a geometric multigrid method on adaptively refined meshes for massively parallel computations. The method uses local smoothing on the refined part of the mesh. Partitioning is achieved by using a space filling curve for the leaf mesh and distributing ancestors in the hierarchy based on the leaves. We present a model of the efficiency of mesh hier… ▽ More We present the design and implementation details of a geometric multigrid method on adaptively refined meshes for massively parallel computations. The method uses local smoothing on the refined part of the mesh. Partitioning is achieved by using a space filling curve for the leaf mesh and distributing ancestors in the hierarchy based on the leaves. We present a model of the efficiency of mesh hierarchy distribution and compare its predictions to runtime measurements. The algorithm is implemented as part of the deal.II finite element library and as such available to the public. △ Less

Submitted 3 August, 2021; v1 submitted 5 April, 2019; originally announced April 2019.

Multilevel Schwarz preconditioners for singularly perturbed symmetric reaction-diffusion systems

Authors: Jose Pablo Lucero Lorca, Guido Kanschat

Abstract: We present robust and highly parallel multilevel non-overlapping Schwarz preconditioners, to solve an interior penalty discontinuous Galerkin finite element discretization of a system of steady state, singularly perturbed reaction-diffusion equations with a singular reaction operator, using a GMRES solver. We provide proofs of convergence for the two-level setting and the multigrid V-cycle as well… ▽ More We present robust and highly parallel multilevel non-overlapping Schwarz preconditioners, to solve an interior penalty discontinuous Galerkin finite element discretization of a system of steady state, singularly perturbed reaction-diffusion equations with a singular reaction operator, using a GMRES solver. We provide proofs of convergence for the two-level setting and the multigrid V-cycle as well as numerical results for a wide range of regimes. △ Less

Submitted 5 September, 2020; v1 submitted 9 November, 2018; originally announced November 2018.

Comments: 19 pages, 5 tables

MSC Class: 65N55 (Primary) 65N30; 65J10; 65F08 (Secondary)

Journal ref: Electron. Trans. Numer. Anal. Volume 54, pp. 89-107, 2021

A C1-mapping based on finite elements on quadrilateral and hexahedral meshes

Authors: Daniel Arndt, Guido Kanschat

Abstract: Finite elements of higher continuity, say conforming in $H^2$ instead of $H^1$, require a mapping from reference cells to mesh cells which is continuously differentiable across cell interfaces. In this article, we propose an algorithm to obtain such mappings given a topologically regular mesh in the standard format of vertex coordinates and a description of the boundary. A variant of the algorithm… ▽ More Finite elements of higher continuity, say conforming in $H^2$ instead of $H^1$, require a mapping from reference cells to mesh cells which is continuously differentiable across cell interfaces. In this article, we propose an algorithm to obtain such mappings given a topologically regular mesh in the standard format of vertex coordinates and a description of the boundary. A variant of the algorithm with orthogonal edges in each vertex is proposed. We introduce necessary modifications in the case of adaptive mesh refinement with nonconforming edges. Furthermore, we discuss efficient storage of the necessary data. △ Less

Submitted 4 October, 2018; originally announced October 2018.

MSC Class: 65N50; 65N30

A Contraction Property of an Adaptive Divergence-Conforming Discontinuous Galerkin Method for the Stokes Problem

Authors: Natasha Sharma, Guido Kanschat

Abstract: We prove the contraction property for two successive loops of the adaptive algorithm for the Stokes problem reducing the error of the velocity. The problem is discretized by a divergence-conforming discontinuous Galerkin method which separates pressure and velocity approximation due to its cochain property. This allows us to establish the quasi-orthogonality property which is crucial for the proof… ▽ More We prove the contraction property for two successive loops of the adaptive algorithm for the Stokes problem reducing the error of the velocity. The problem is discretized by a divergence-conforming discontinuous Galerkin method which separates pressure and velocity approximation due to its cochain property. This allows us to establish the quasi-orthogonality property which is crucial for the proof of the contraction. We also establish the quasi-optimal complexity of the adaptive algorithm in terms of the degrees of freedom. △ Less

Submitted 23 July, 2018; originally announced July 2018.

MSC Class: 65N30

A finite element method with strong mass conservation for Biot's linear consolidation model

Authors: Beatrice Riviere, Guido Kanschat

Abstract: An H(div) conforming finite element method for solving the linear Biot equations is analyzed. Formulations for the standard mixed method are combined with formulation of interior penalty discontinuous Galerkin method to obtain a consistent scheme. Optimal convergence rates are obtained. An H(div) conforming finite element method for solving the linear Biot equations is analyzed. Formulations for the standard mixed method are combined with formulation of interior penalty discontinuous Galerkin method to obtain a consistent scheme. Optimal convergence rates are obtained. △ Less

Submitted 20 December, 2017; originally announced December 2017.

MSC Class: 65M60; 74F10

Geometric Multigrid for Darcy and Brinkman models of flows in highly heterogeneous porous media: A numerical study

Authors: Guido Kanschat, Raytcho Lazarov, Youli Mao

Abstract: We apply geometric multigrid methods for the finite element approximation of flow problems governed by Darcy and Brinkman systems used in modeling highly heterogeneous porous media. The method is based on divergence-conforming discontinuous Galerkin methods and overlapping, patch based domain decomposition smoothers. We show in benchmark experiments that the method is robust with respect to mesh s… ▽ More We apply geometric multigrid methods for the finite element approximation of flow problems governed by Darcy and Brinkman systems used in modeling highly heterogeneous porous media. The method is based on divergence-conforming discontinuous Galerkin methods and overlapping, patch based domain decomposition smoothers. We show in benchmark experiments that the method is robust with respect to mesh size and contrast of permeability for highly heterogeneous media. △ Less

Submitted 20 May, 2016; v1 submitted 15 February, 2016; originally announced February 2016.

Comments: 15 pages, 8 figures

MSC Class: 65N

Multigrid methods for Hdiv-conforming discontinuous Galerkin methods for the Stokes equations

Authors: Guido Kanschat, Youli Mao

Abstract: A multigrid method for the Stokes system discretized with an Hdiv-conforming discontinuous Galerkin method is presented. It acts on the combined velocity and pressure spaces and thus does not need a Schur complement approximation. The smoothers used are of overlapping Schwarz type and employ a local Helmholtz decomposition. Additionally, we use the fact that the discretization provides nested dive… ▽ More A multigrid method for the Stokes system discretized with an Hdiv-conforming discontinuous Galerkin method is presented. It acts on the combined velocity and pressure spaces and thus does not need a Schur complement approximation. The smoothers used are of overlapping Schwarz type and employ a local Helmholtz decomposition. Additionally, we use the fact that the discretization provides nested divergence free subspaces. We present the convergence analysis and numerical evidence that convergence rates are not only independent of mesh size, but also reasonably small. △ Less

Submitted 24 January, 2015; originally announced January 2015.

MSC Class: 65N55

Journal ref: J. Numer. Math. 23(1), pp. 51-66, 2015

The deal.II Library, Version 8.1

Authors: Wolfgang Bangerth, Timo Heister, Luca Heltai, Guido Kanschat, Martin Kronbichler, Matthias Maier, Bruno Turcksin, Toby D. Young

Abstract: This paper provides an overview of the new features of the finite element library deal.II version 8.1. This paper provides an overview of the new features of the finite element library deal.II version 8.1. △ Less

Submitted 31 December, 2013; v1 submitted 8 December, 2013; originally announced December 2013.

Comments: v4: for deal.II version 8.1 v3: minor fixes. v2: correct the citation inside the article