A Black-Box Algorithm for Fast Matrix Assembly in Isogeometric Analysis
C. Hofreither. NuMa-Report No. 2017-02. nstitute of Computational Mathematics, Johannes Kepler University, Linz, Austria, (April 2017)
DOI: 10.1016/j.cma.2018.01.014
Abstract
We present a fast algorithm for assembling stiffness matrices in Isogeometric Analysis with tensor product spline spaces. The procedure exploits
the facts that (a) such matrices have block-banded structure, and (b) they
often have low Kronecker rank. Combined, these two properties allow us
to reorder the nonzero entries of the stiffness matrix into a relatively small,
dense matrix or tensor of low rank. A suitable black-box low-rank approximation algorithm is then applied to this matrix or tensor. This allows
us to approximate the nonzero entries of the stiffness matrix while explicitly computing only relatively few of them, leading to a fast assembly
procedure.
The algorithm does not require any further knowledge of the used
spline spaces, the geometry transform, or the partial differential equation,
and thus is black-box in nature. Existing assembling routines can be
reused with minor modifications. A reference implementation is provided
which can be integrated into existing code.
Numerical examples demonstrate significant speedups over a standard
Gauss quadrature assembler for several geometries in two and three dimensions. The runtime scales sublinearly with the number of degrees of
freedom in a large pre-asymptotic regime.
%0 Report
%1 Hofreither2017BlackBox
%A Hofreither, Clemens
%C Linz, Austria
%D 2017
%J Computer Methods in Applied Mechanics and Engineering
%K 65m60-pdes-ibvps-finite-elements 65n30-pdes-bvps-finite-elements 76m10-finite-element-methods-in-fluid-mechanics
%N NuMa-Report No. 2017-02
%R 10.1016/j.cma.2018.01.014
%T A Black-Box Algorithm for Fast Matrix Assembly in Isogeometric Analysis
%U http://dx.doi.org/10.1016/j.cma.2018.01.014
%X We present a fast algorithm for assembling stiffness matrices in Isogeometric Analysis with tensor product spline spaces. The procedure exploits
the facts that (a) such matrices have block-banded structure, and (b) they
often have low Kronecker rank. Combined, these two properties allow us
to reorder the nonzero entries of the stiffness matrix into a relatively small,
dense matrix or tensor of low rank. A suitable black-box low-rank approximation algorithm is then applied to this matrix or tensor. This allows
us to approximate the nonzero entries of the stiffness matrix while explicitly computing only relatively few of them, leading to a fast assembly
procedure.
The algorithm does not require any further knowledge of the used
spline spaces, the geometry transform, or the partial differential equation,
and thus is black-box in nature. Existing assembling routines can be
reused with minor modifications. A reference implementation is provided
which can be integrated into existing code.
Numerical examples demonstrate significant speedups over a standard
Gauss quadrature assembler for several geometries in two and three dimensions. The runtime scales sublinearly with the number of degrees of
freedom in a large pre-asymptotic regime.
@techreport{Hofreither2017BlackBox,
abstract = {{We present a fast algorithm for assembling stiffness matrices in Isogeometric Analysis with tensor product spline spaces. The procedure exploits
the facts that (a) such matrices have block-banded structure, and (b) they
often have low Kronecker rank. Combined, these two properties allow us
to reorder the nonzero entries of the stiffness matrix into a relatively small,
dense matrix or tensor of low rank. A suitable black-box low-rank approximation algorithm is then applied to this matrix or tensor. This allows
us to approximate the nonzero entries of the stiffness matrix while explicitly computing only relatively few of them, leading to a fast assembly
procedure.
The algorithm does not require any further knowledge of the used
spline spaces, the geometry transform, or the partial differential equation,
and thus is black-box in nature. Existing assembling routines can be
reused with minor modifications. A reference implementation is provided
which can be integrated into existing code.
Numerical examples demonstrate significant speedups over a standard
Gauss quadrature assembler for several geometries in two and three dimensions. The runtime scales sublinearly with the number of degrees of
freedom in a large pre-asymptotic regime.}},
added-at = {2019-03-01T00:11:50.000+0100},
address = {Linz, Austria},
author = {Hofreither, Clemens},
biburl = {https://www.bibsonomy.org/bibtex/2c4fb751c951215af03c012f85817e538/gdmcbain},
citeulike-article-id = {14622885},
citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.cma.2018.01.014},
doi = {10.1016/j.cma.2018.01.014},
institution = {nstitute of Computational Mathematics, Johannes Kepler University},
interhash = {f125f2366b08a5a944f5e28e8ba9716d},
intrahash = {c4fb751c951215af03c012f85817e538},
journal = {Computer Methods in Applied Mechanics and Engineering},
keywords = {65m60-pdes-ibvps-finite-elements 65n30-pdes-bvps-finite-elements 76m10-finite-element-methods-in-fluid-mechanics},
month = apr,
number = {NuMa-Report No. 2017-02},
posted-at = {2018-08-07 02:28:10},
priority = {5},
timestamp = {2019-03-01T00:11:50.000+0100},
title = {{A Black-Box Algorithm for Fast Matrix Assembly in Isogeometric Analysis}},
url = {http://dx.doi.org/10.1016/j.cma.2018.01.014},
year = 2017
}