Quasi-optimal elimination trees for 2D grids with singularities
We construct quasi-optimal elimination trees for 2D finite element meshes with singularities.These trees minimize the complexity of the solution of the discrete system. The computational cost estimates of the elimination process model the execution of the multifrontal algorithms in serial and in par...
| Main Authors: | , , , , , , , , , , , |
|---|---|
| Format: | Journal Article |
| Published: |
2015
|
| Online Access: | http://hdl.handle.net/20.500.11937/48957 |
| _version_ | 1848758132442923008 |
|---|---|
| author | Paszynska, A. Paszynski, M. Jopek, K. Wofniak, M. Goik, D. Gurgul, P. Aboueisha, H. Moshkov, M. Calo, Victor Lenharth, A. Nguyen, D. Pingali, K. |
| author_facet | Paszynska, A. Paszynski, M. Jopek, K. Wofniak, M. Goik, D. Gurgul, P. Aboueisha, H. Moshkov, M. Calo, Victor Lenharth, A. Nguyen, D. Pingali, K. |
| author_sort | Paszynska, A. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | We construct quasi-optimal elimination trees for 2D finite element meshes with singularities.These trees minimize the complexity of the solution of the discrete system. The computational cost estimates of the elimination process model the execution of the multifrontal algorithms in serial and in parallel shared-memory executions. Since the meshes considered are a subspace of all possible mesh partitions, we call these minimizers quasi-optimal.We minimize the cost functionals using dynamic programming. Finding these minimizers is more computationally expensive than solving the original algebraic system. Nevertheless, from the insights provided by the analysis of the dynamic programming minima, we propose a heuristic construction of the elimination trees that has cost O(log(Ne log(Ne)), where N e is the number of elements in the mesh.We show that this heuristic ordering has similar computational cost to the quasi-optimal elimination trees found with dynamic programming and outperforms state-of-the-art alternatives in our numerical experiments. |
| first_indexed | 2025-11-14T09:39:08Z |
| format | Journal Article |
| id | curtin-20.500.11937-48957 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T09:39:08Z |
| publishDate | 2015 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-489572017-09-13T15:45:38Z Quasi-optimal elimination trees for 2D grids with singularities Paszynska, A. Paszynski, M. Jopek, K. Wofniak, M. Goik, D. Gurgul, P. Aboueisha, H. Moshkov, M. Calo, Victor Lenharth, A. Nguyen, D. Pingali, K. We construct quasi-optimal elimination trees for 2D finite element meshes with singularities.These trees minimize the complexity of the solution of the discrete system. The computational cost estimates of the elimination process model the execution of the multifrontal algorithms in serial and in parallel shared-memory executions. Since the meshes considered are a subspace of all possible mesh partitions, we call these minimizers quasi-optimal.We minimize the cost functionals using dynamic programming. Finding these minimizers is more computationally expensive than solving the original algebraic system. Nevertheless, from the insights provided by the analysis of the dynamic programming minima, we propose a heuristic construction of the elimination trees that has cost O(log(Ne log(Ne)), where N e is the number of elements in the mesh.We show that this heuristic ordering has similar computational cost to the quasi-optimal elimination trees found with dynamic programming and outperforms state-of-the-art alternatives in our numerical experiments. 2015 Journal Article http://hdl.handle.net/20.500.11937/48957 10.1155/2015/303024 fulltext |
| spellingShingle | Paszynska, A. Paszynski, M. Jopek, K. Wofniak, M. Goik, D. Gurgul, P. Aboueisha, H. Moshkov, M. Calo, Victor Lenharth, A. Nguyen, D. Pingali, K. Quasi-optimal elimination trees for 2D grids with singularities |
| title | Quasi-optimal elimination trees for 2D grids with singularities |
| title_full | Quasi-optimal elimination trees for 2D grids with singularities |
| title_fullStr | Quasi-optimal elimination trees for 2D grids with singularities |
| title_full_unstemmed | Quasi-optimal elimination trees for 2D grids with singularities |
| title_short | Quasi-optimal elimination trees for 2D grids with singularities |
| title_sort | quasi-optimal elimination trees for 2d grids with singularities |
| url | http://hdl.handle.net/20.500.11937/48957 |