A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities

Maciej R. Paszyński; Victor M. Calo; David Pardo

doi:10.1016/j.camwa.2013.02.006

A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities

Maciej R. Paszyński, Victor M. Calo, David Pardo

King Abdullah University of Science and Technology

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

This paper describes a direct solver algorithm for a sequence of finite element meshes that are h-refined towards one or several point singularities. For such a sequence of grids, the solver delivers linear computational cost O(N) in terms of CPU time and memory with respect to the number of unknowns N. The linear computational cost is achieved by utilizing the recursive structure provided by the sequence of h-adaptive grids with a special construction of the elimination tree that allows for reutilization of previously computed partial LU (or Cholesky) factorizations over the entire unrefined part of the computational mesh. The reutilization technique reduces the computational cost of the entire sequence of h-refined grids from O(N2) down to O(N). Theoretical estimates are illustrated with numerical results on two- and three-dimensional model problems exhibiting one or several point singularities. © 2013 Elsevier Ltd. All rights reserved.

Original language	English (US)
Pages (from-to)	1140-1151
Number of pages	12
Journal	Computers and Mathematics with Applications
Volume	65
Issue number	8
DOIs	https://doi.org/10.1016/j.camwa.2013.02.006
State	Published - Apr 2013

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: MP was supported by Polish National Science Center grants no NN 519 447739 and NN 519 405737. DP was partially funded by the Project of the Spanish Ministry of Sciences and Innovation MTM2010-16511, the Laboratory of Mathematics (UFI 11/52), and the Ibero-American Project CYTED 2011 (P711RT0278). MP and DP were partially supported by the Center for Numerical Porous Media at KAUST.

ASJC Scopus subject areas

Modeling and Simulation
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/j.camwa.2013.02.006

Cite this

@article{88700628c9af4fe1b611fb09f66f1ebc,

title = "A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities",

abstract = "This paper describes a direct solver algorithm for a sequence of finite element meshes that are h-refined towards one or several point singularities. For such a sequence of grids, the solver delivers linear computational cost O(N) in terms of CPU time and memory with respect to the number of unknowns N. The linear computational cost is achieved by utilizing the recursive structure provided by the sequence of h-adaptive grids with a special construction of the elimination tree that allows for reutilization of previously computed partial LU (or Cholesky) factorizations over the entire unrefined part of the computational mesh. The reutilization technique reduces the computational cost of the entire sequence of h-refined grids from O(N2) down to O(N). Theoretical estimates are illustrated with numerical results on two- and three-dimensional model problems exhibiting one or several point singularities. {\textcopyright} 2013 Elsevier Ltd. All rights reserved.",

author = "Paszy{\'n}ski, {Maciej R.} and Calo, {Victor M.} and David Pardo",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: MP was supported by Polish National Science Center grants no NN 519 447739 and NN 519 405737. DP was partially funded by the Project of the Spanish Ministry of Sciences and Innovation MTM2010-16511, the Laboratory of Mathematics (UFI 11/52), and the Ibero-American Project CYTED 2011 (P711RT0278). MP and DP were partially supported by the Center for Numerical Porous Media at KAUST.",

year = "2013",

month = apr,

doi = "10.1016/j.camwa.2013.02.006",

language = "English (US)",

volume = "65",

pages = "1140--1151",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities

AU - Paszyński, Maciej R.

AU - Calo, Victor M.

AU - Pardo, David

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: MP was supported by Polish National Science Center grants no NN 519 447739 and NN 519 405737. DP was partially funded by the Project of the Spanish Ministry of Sciences and Innovation MTM2010-16511, the Laboratory of Mathematics (UFI 11/52), and the Ibero-American Project CYTED 2011 (P711RT0278). MP and DP were partially supported by the Center for Numerical Porous Media at KAUST.

PY - 2013/4

Y1 - 2013/4

N2 - This paper describes a direct solver algorithm for a sequence of finite element meshes that are h-refined towards one or several point singularities. For such a sequence of grids, the solver delivers linear computational cost O(N) in terms of CPU time and memory with respect to the number of unknowns N. The linear computational cost is achieved by utilizing the recursive structure provided by the sequence of h-adaptive grids with a special construction of the elimination tree that allows for reutilization of previously computed partial LU (or Cholesky) factorizations over the entire unrefined part of the computational mesh. The reutilization technique reduces the computational cost of the entire sequence of h-refined grids from O(N2) down to O(N). Theoretical estimates are illustrated with numerical results on two- and three-dimensional model problems exhibiting one or several point singularities. © 2013 Elsevier Ltd. All rights reserved.

AB - This paper describes a direct solver algorithm for a sequence of finite element meshes that are h-refined towards one or several point singularities. For such a sequence of grids, the solver delivers linear computational cost O(N) in terms of CPU time and memory with respect to the number of unknowns N. The linear computational cost is achieved by utilizing the recursive structure provided by the sequence of h-adaptive grids with a special construction of the elimination tree that allows for reutilization of previously computed partial LU (or Cholesky) factorizations over the entire unrefined part of the computational mesh. The reutilization technique reduces the computational cost of the entire sequence of h-refined grids from O(N2) down to O(N). Theoretical estimates are illustrated with numerical results on two- and three-dimensional model problems exhibiting one or several point singularities. © 2013 Elsevier Ltd. All rights reserved.

UR - http://hdl.handle.net/10754/562704

UR - http://arxiv.org/abs/arXiv:1212.1992v1

UR - http://www.scopus.com/inward/record.url?scp=84876099737&partnerID=8YFLogxK

U2 - 10.1016/j.camwa.2013.02.006

DO - 10.1016/j.camwa.2013.02.006

M3 - Article

SN - 0898-1221

VL - 65

SP - 1140

EP - 1151

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 8

ER -

A direct solver with reutilization of LU factorizations for h-adaptive finite element grids with point singularities

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this