You searched for subject:(Algebraic Multigrid).
Showing records 1 – 28 of
28 total matches.
No search limiters apply to these results.
University of Colorado
1.
Park, Minho.
Relaxation-Corrected Bootstrap Algebraic Multigrid (rBAMG).
Degree: PhD, Applied Mathematics, 2010, University of Colorado
URL: https://scholar.colorado.edu/appm_gradetds/10 
► Bootstrap Algebraic Multigrid (BAMG) is a multigrid-based solver for matrix equations of the form Ax = b. Its aim is to automatically determine the…
(more)
▼ Bootstrap
Algebraic Multigrid (BAMG) is a
multigrid-based solver for matrix equations of the form Ax = b. Its aim is to automatically determine the interpolation weights used in
algebraic multigrid (AMG) by locally fitting a set of test vectors that have been relaxed as solutions to the corresponding homogeneous equation, Ax = 0. This thesis introduces an indirect operator based interpolation scheme for BAMG that determines the interpolation weights indirectly by “collapsing” the unwanted connections in “operator interpolation”. Compared to BAMG, this
indirect BAMG approach (
iBAMG) is more in the spirit of classical AMG, which collapses unwanted connections in operator interpolation based on the (restrictive) assumption that smooth error is locally constant.
This thesis also develops another form of BAMG, called
rBAMG, that involves modifying the least-squares process by temporarily relaxing on the test vectors at the fine-grid interpolation points. The theory here shows that, under fairly general conditions,
iBAMG and
rBAMG are equivalent. Simplicity and potentially greater generality favor
rBAMG, so this algorithm is at the focus of the numerical performance study here.
The
rBAMG setup process involves several components that are developed in this thesis.
Besides the new least-squares principle involving the residuals of the test vectors, a simple extrapolation scheme is developed to accurately estimate the convergence factors of the evolving AMG solver. Such a capability is essential to effective development of a fast solver, and the approach introduced here proves to be much more effective than the conventional approach of just observing successive error reduction factors. Another component of the setup process is the use of the current V-cycle to ensure its effectiveness or, when poor convergence is observed, to expose error components that are not being properly attenuated. How we coordinate use of these evolving error components together with the original test vectors to direct the setup process is a critical issue to
rBAMG’s effectiveness. Another related component is the scaling and recombination Ritz process that targets the so-called weak approximation property in an attempt to reveal the important elements of these evolving error and test vector spaces. The details of the components used here are spelled out in what follows.
The study of
rBAMG here is an attempt to systematically analyze the behavior of the algorithm in terms relative to several parameters. The focus here is on the number of test vectors, the number of relaxations applied to them, and the dimension of the matrix to which the scheme is applied. A large number of other parameters and options could also be considered, including different cycling strategies, other coarsening strategies (e. g., computing several eigenvector approximations on coarse levels), different numbers of relaxation sweeps on coarse levels, different…
Advisors/Committee Members: Stephen F. McCormick, Thomas A. Manteuffel, Marian Brezina.
Subjects/Keywords: Adaptive Multigrid; Algebraic Multigrid; Bootstrap Algebraic Multigrid; Convergence Estimate; Iterative Methods; Multigrid; Applied Mathematics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Park, M. (2010). Relaxation-Corrected Bootstrap Algebraic Multigrid (rBAMG). (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/10
Chicago Manual of Style (16th Edition):
Park, Minho. “Relaxation-Corrected Bootstrap Algebraic Multigrid (rBAMG).” 2010. Doctoral Dissertation, University of Colorado. Accessed March 05, 2021.
https://scholar.colorado.edu/appm_gradetds/10.
MLA Handbook (7th Edition):
Park, Minho. “Relaxation-Corrected Bootstrap Algebraic Multigrid (rBAMG).” 2010. Web. 05 Mar 2021.
Vancouver:
Park M. Relaxation-Corrected Bootstrap Algebraic Multigrid (rBAMG). [Internet] [Doctoral dissertation]. University of Colorado; 2010. [cited 2021 Mar 05].
Available from: https://scholar.colorado.edu/appm_gradetds/10.
Council of Science Editors:
Park M. Relaxation-Corrected Bootstrap Algebraic Multigrid (rBAMG). [Doctoral Dissertation]. University of Colorado; 2010. Available from: https://scholar.colorado.edu/appm_gradetds/10
Penn State University
2.
Cao, Fei.
Generalized Bootstrap Algebraic Multigrid.
Degree: 2017, Penn State University
URL: https://submit-etda.libraries.psu.edu/catalog/14776fwc5045
► In this thesis, we consider a classical algebraic multigrid form of optimal interpolation that directly minimizes the two-grid convergence rate and compare it with a…
(more)
▼ In this thesis, we consider a classical
algebraic multigrid form of optimal interpolation that directly minimizes the two-grid convergence rate and compare it with a so-called ideal interpolation that minimizes a certain weak approximation property of the coarse space. We study compatible relaxation type estimates for the quality of the coarse grid and derive a new sharp measure using optimal interpolation that provides a guaranteed lower bound on the convergence rate of the resulting two-grid method for a given grid. Also we design an adaptive coarsening algorithm based on this sharp form of compatible relaxation. The resulting coarsening algorithm aims to find a sparse representation (changing of basis) for the coarse space defined by the optimal interpolation operator. In addition, we design a generalized bootstrap
algebraic multigrid setup algorithm that computes a sparse approximation to the optimal interpolation matrix. We demonstrate numerically that the bootstrap
algebraic multigrid method with sparse interpolation matrix
(and spanning multiple levels) converges faster than the two-grid method with the standard ideal interpolation (a dense matrix) for various scalar diffusion problems with highly varying diffusion coefficient and we show the general usage of our algorithm by applying also to elasticity problem.
Advisors/Committee Members: James Joseph Brannick, Dissertation Advisor/Co-Advisor, James Joseph Brannick, Committee Chair/Co-Chair, Jinchao Xu, Committee Member, Yuxi Zheng, Committee Member, Lyle Norman Long, Outside Member.
Subjects/Keywords: algebraic multigrid; compatible relaxation; bootstrap algebraic multigrid; optimal interpolation
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Cao, F. (2017). Generalized Bootstrap Algebraic Multigrid. (Thesis). Penn State University. Retrieved from https://submit-etda.libraries.psu.edu/catalog/14776fwc5045
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Cao, Fei. “Generalized Bootstrap Algebraic Multigrid.” 2017. Thesis, Penn State University. Accessed March 05, 2021.
https://submit-etda.libraries.psu.edu/catalog/14776fwc5045.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Cao, Fei. “Generalized Bootstrap Algebraic Multigrid.” 2017. Web. 05 Mar 2021.
Vancouver:
Cao F. Generalized Bootstrap Algebraic Multigrid. [Internet] [Thesis]. Penn State University; 2017. [cited 2021 Mar 05].
Available from: https://submit-etda.libraries.psu.edu/catalog/14776fwc5045.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Cao F. Generalized Bootstrap Algebraic Multigrid. [Thesis]. Penn State University; 2017. Available from: https://submit-etda.libraries.psu.edu/catalog/14776fwc5045
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Penn State University
3.
Zhang, Hongxuan.
ALGEBRAIC MULTIGRID METHODS AND THEIR APPLICATIONS.
Degree: 2017, Penn State University
URL: https://submit-etda.libraries.psu.edu/catalog/14766huz114
► Algebraic MultiGrid (AMG) method, is one of the most efficient numerical techniques to solve large-scale linear system, especially for those arising from discretization of systems…
(more)
▼ Algebraic MultiGrid (AMG) method, is one of the most efficient numerical techniques to solve large-scale linear system, especially for those arising from discretization of systems of partial differential equations (PDEs). In this work, we try to understand how and why an
algebraic multigrid method in a more abstract level. We develop a unified framework and theory that can be used to derive and analyze different
algebraic multigrid methods in a coherent manner. Given a smoother R for a matrix A, such as Gauss-Seidel or Jacobi, it is well-known that the optimal coarse space of dimension n
c is the span of the eigen-vectors corresponding to the first n
c eigen-values of \bar RA (with \bar R=R+R
T-RTAR). We prove that this optimal coarse space can be obtained by a constrained trace-minimization problem for a matrix associated with \bar RA and demonstrate that coarse spaces of most of existing AMG methods can be viewed some approximate solution of this trace-minimization problem. Furthermore, we develop a general approach to the construction of a quasi-optimal coarse space and we prove that under appropriate assumptions the resulting two-level AMG method for the underlying linear system converges uniformly with respect to the size of the problem, the coefficient variation, and the anisotropy. Our theory applies to most existing
multigrid methods, including the standard geometric
multigrid method, the classic AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG, and spectral AMGe. Finally, we apply AMG methods to two application problems, one is on electrokinetics flow and the other is on reservoir simulation, which provide numerical results to demonstrate the efficiency and robustness of AMG methods.
Advisors/Committee Members: Jinchao Xu, Dissertation Advisor/Co-Advisor, Jinchao Xu, Committee Chair/Co-Chair, Ludmil Tomov Zikatanov, Committee Member, James Joseph Brannick, Committee Member, Yilin Wang, Outside Member.
Subjects/Keywords: Algebraic Multigrid; Numerical Linear Algebra; Numerical Analysis
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Zhang, H. (2017). ALGEBRAIC MULTIGRID METHODS AND THEIR APPLICATIONS. (Thesis). Penn State University. Retrieved from https://submit-etda.libraries.psu.edu/catalog/14766huz114
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Zhang, Hongxuan. “ALGEBRAIC MULTIGRID METHODS AND THEIR APPLICATIONS.” 2017. Thesis, Penn State University. Accessed March 05, 2021.
https://submit-etda.libraries.psu.edu/catalog/14766huz114.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Zhang, Hongxuan. “ALGEBRAIC MULTIGRID METHODS AND THEIR APPLICATIONS.” 2017. Web. 05 Mar 2021.
Vancouver:
Zhang H. ALGEBRAIC MULTIGRID METHODS AND THEIR APPLICATIONS. [Internet] [Thesis]. Penn State University; 2017. [cited 2021 Mar 05].
Available from: https://submit-etda.libraries.psu.edu/catalog/14766huz114.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Zhang H. ALGEBRAIC MULTIGRID METHODS AND THEIR APPLICATIONS. [Thesis]. Penn State University; 2017. Available from: https://submit-etda.libraries.psu.edu/catalog/14766huz114
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Penn State University
4.
Chen, Yao.
Algebraic Multilevel Methods for Graph Laplacians.
Degree: 2012, Penn State University
URL: https://submit-etda.libraries.psu.edu/catalog/15362
► This dissertation presents estimates of the convergence rate and computational complexity of an algebraic multilevel preconditioner of graph Laplacian problems. The aim is to construct…
(more)
▼ This dissertation presents estimates of the convergence rate and computational complexity of an
algebraic multilevel preconditioner of graph Laplacian problems. The aim is to construct fast and robust multilevel solvers, and this is achieved by balancing the convergence rate and the complexity of an aggregation based multilevel method. The main theoretical result consists of two parts: first, the relation between a graph partitioning and the convergence rate of the corresponding aggregation based two-level method is established; next, a multilevel method with polynomial coarse level corrections is constructed in the way that both its convergence rate and its complexity can be estimated simultaneously. Numerical tests further indicate the sharpness of the theoretical estimates. Some other interesting results, including a generalized definition of strength of connection, an optimal convergence condition of the
algebraic multilevel iterations, and parallel implementations of the numerical solvers, are also addressed.
Advisors/Committee Members: James Joseph Brannick, Committee Chair/Co-Chair, Ludmil Tomov Zikatanov, Dissertation Advisor/Co-Advisor, Jinchao Xu, Committee Member, Jesse Louis Barlow, Special Member.
Subjects/Keywords: Algebraic Multigrid Methods; Graph Laplacians; Parallel Algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Chen, Y. (2012). Algebraic Multilevel Methods for Graph Laplacians. (Thesis). Penn State University. Retrieved from https://submit-etda.libraries.psu.edu/catalog/15362
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Chen, Yao. “Algebraic Multilevel Methods for Graph Laplacians.” 2012. Thesis, Penn State University. Accessed March 05, 2021.
https://submit-etda.libraries.psu.edu/catalog/15362.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Chen, Yao. “Algebraic Multilevel Methods for Graph Laplacians.” 2012. Web. 05 Mar 2021.
Vancouver:
Chen Y. Algebraic Multilevel Methods for Graph Laplacians. [Internet] [Thesis]. Penn State University; 2012. [cited 2021 Mar 05].
Available from: https://submit-etda.libraries.psu.edu/catalog/15362.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Chen Y. Algebraic Multilevel Methods for Graph Laplacians. [Thesis]. Penn State University; 2012. Available from: https://submit-etda.libraries.psu.edu/catalog/15362
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Illinois – Urbana-Champaign
5.
Gahvari, Hormozd.
Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling.
Degree: PhD, 0112, 2014, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/50516
► With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run…
(more)
▼ With single-core speeds no longer rising, dramatically increased parallelism is now the means of getting more performance from supercomputers. The current generation of algorithms run on these machines will have to adapt to this new landscape. In this dissertation, we focus on
algebraic multigrid (AMG), a popular linear solver with many scientific and engineering applications. AMG has the attractive property of requiring work that is linear in the number of unknowns. However, it also has substantial communication requirements that impede its scalability on emerging architectures.
In our treatment of AMG, we make heavy use of performance modeling, developing a methodology we like to call, ``applied performance modeling,'' that drives how we analyze and adjust AMG to improve its performance and scalability. The fundamental idea is that straightforward performance models can be used to analyze applications and architectures and draw startlingly powerful conclusions about them. We develop such models for AMG and use them to explain performance difficulties on emerging machines, analyze a large body of past work in adapting
multigrid methods to massively parallel machines, and then perform a pair of practical tasks: guiding an algorithm that redistributes data to trade communication for computation, and informing the selection of thread/task mixes when using a hybrid programming model.
Our performance models accurately predict the performance of the AMG solve cycle on multiple platforms, capturing the application and architectural features behind the observed performance, and are easily extended to cover new platforms and AMG algorithms. The model-guided data redistribution yields significant improvements, and the suggestions provided for thread/task mixes enable users to avoid selecting ones that would perform poorly. We are encouraged by our results so far, and expect our work to be of continued use to AMG and to other applications in the future.
Advisors/Committee Members: Gropp, William D. (advisor), Gropp, William D. (Committee Chair), Heath, Michael T. (committee member), Olson, Luke N. (committee member), Vanka, Surya Pratap (committee member), Yang, Ulrike M. (committee member).
Subjects/Keywords: Algebraic Multigrid; Performance Modeling; Massively Parallel Architectures
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Gahvari, H. (2014). Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/50516
Chicago Manual of Style (16th Edition):
Gahvari, Hormozd. “Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling.” 2014. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 05, 2021.
http://hdl.handle.net/2142/50516.
MLA Handbook (7th Edition):
Gahvari, Hormozd. “Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling.” 2014. Web. 05 Mar 2021.
Vancouver:
Gahvari H. Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2014. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/2142/50516.
Council of Science Editors:
Gahvari H. Improving the performance and scalability of algebraic multigrid solvers through applied performance modeling. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2014. Available from: http://hdl.handle.net/2142/50516
University of Pretoria
6.
[No author].
An algebraic multigrid solution strategy for efficient
solution of free-surface flows
.
Degree: 2011, University of Pretoria
URL: http://upetd.up.ac.za/thesis/available/etd-09222011-093322/
► Free-surface modelling (FSM) is a highly relevant and computationally intensive area of study in modern computational fluid dynamics. The Elemental software suite currently under development…
(more)
▼ Free-surface modelling (FSM) is a highly relevant
and computationally intensive area of study in modern computational
fluid dynamics. The Elemental software suite currently under
development offers FSMcapability, and employs a preconditioned
GMRES solver in an attempt to effect fast solution times. In terms
of potential solver performance however,
multigrid methods can be
considered state-of-the-art. This work details the investigation
into the use of AlgebraicMultigrid (AMG) as a high performance
solver tool for use as black box plug-in for Elemental FSM. Special
attention was given to the development of novel and robust methods
of addressing AMG setup costs in addition to transcribing the
solver to efficient C++ object-oriented code. This led to the
development of the so-called Freeze extension of the basic
algebraic multigrid method in an object-oriented C++ programming
environment. The newly developed Freeze method reduces setup costs
by periodically performing the setup procedure in an automatic and
robust manner. The developed technology was evaluated in terms of
robustness, stability and speed by applying it to benchmark FSM
problems on structured and unstructured meshes of various sizes.
This evaluation yielded a number of conclusive findings. First, the
developed Freeze method reduced setup times by an order of
magnitude. Second, the developed AMG solver offered substantial
performance increases over the preconditioned GMRES method. In this
way, it is proposed that this work has furthered the
state-of-the-art of
algebraic multigrid methods applied in the
context of free-surface modelling.
Advisors/Committee Members: Dr A G Malan (advisor), Dr D N Wilke (advisor).
Subjects/Keywords: Algebraic;
Multigrid solution strategy;
Free-surface flows;
UCTD
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
author], [. (2011). An algebraic multigrid solution strategy for efficient
solution of free-surface flows
. (Masters Thesis). University of Pretoria. Retrieved from http://upetd.up.ac.za/thesis/available/etd-09222011-093322/
Chicago Manual of Style (16th Edition):
author], [No. “An algebraic multigrid solution strategy for efficient
solution of free-surface flows
.” 2011. Masters Thesis, University of Pretoria. Accessed March 05, 2021.
http://upetd.up.ac.za/thesis/available/etd-09222011-093322/.
MLA Handbook (7th Edition):
author], [No. “An algebraic multigrid solution strategy for efficient
solution of free-surface flows
.” 2011. Web. 05 Mar 2021.
Vancouver:
author] [. An algebraic multigrid solution strategy for efficient
solution of free-surface flows
. [Internet] [Masters thesis]. University of Pretoria; 2011. [cited 2021 Mar 05].
Available from: http://upetd.up.ac.za/thesis/available/etd-09222011-093322/.
Council of Science Editors:
author] [. An algebraic multigrid solution strategy for efficient
solution of free-surface flows
. [Masters Thesis]. University of Pretoria; 2011. Available from: http://upetd.up.ac.za/thesis/available/etd-09222011-093322/
University of Pretoria
7.
Van den Bergh, Wilhelm
J.
An algebraic
multigrid solution strategy for efficient solution of free-surface
flows.
Degree: Mechanical and Aeronautical
Engineering, 2011, University of Pretoria
URL: http://hdl.handle.net/2263/28124
► Free-surface modelling (FSM) is a highly relevant and computationally intensive area of study in modern computational fluid dynamics. The Elemental software suite currently under development…
(more)
▼ Free-surface modelling (FSM) is a highly relevant and
computationally intensive area of study in modern computational
fluid dynamics. The Elemental software suite currently under
development offers FSMcapability, and employs a preconditioned
GMRES solver in an attempt to effect fast solution times. In terms
of potential solver performance however,
multigrid methods can be
considered state-of-the-art. This work details the investigation
into the use of AlgebraicMultigrid (AMG) as a high performance
solver tool for use as black box plug-in for Elemental FSM. Special
attention was given to the development of novel and robust methods
of addressing AMG setup costs in addition to transcribing the
solver to efficient C++ object-oriented code. This led to the
development of the so-called Freeze extension of the basic
algebraic multigrid method in an object-oriented C++ programming
environment. The newly developed Freeze method reduces setup costs
by periodically performing the setup procedure in an automatic and
robust manner. The developed technology was evaluated in terms of
robustness, stability and speed by applying it to benchmark FSM
problems on structured and unstructured meshes of various sizes.
This evaluation yielded a number of conclusive findings. First, the
developed Freeze method reduced setup times by an order of
magnitude. Second, the developed AMG solver offered substantial
performance increases over the preconditioned GMRES method. In this
way, it is proposed that this work has furthered the
state-of-the-art of
algebraic multigrid methods applied in the
context of free-surface modelling.
Advisors/Committee Members: Dr A G Malan (advisor), Dr D N Wilke (advisor).
Subjects/Keywords: Algebraic; Multigrid
solution strategy; Free-surface
flows;
UCTD
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Van den Bergh, W. (2011). An algebraic
multigrid solution strategy for efficient solution of free-surface
flows. (Masters Thesis). University of Pretoria. Retrieved from http://hdl.handle.net/2263/28124
Chicago Manual of Style (16th Edition):
Van den Bergh, Wilhelm. “An algebraic
multigrid solution strategy for efficient solution of free-surface
flows.” 2011. Masters Thesis, University of Pretoria. Accessed March 05, 2021.
http://hdl.handle.net/2263/28124.
MLA Handbook (7th Edition):
Van den Bergh, Wilhelm. “An algebraic
multigrid solution strategy for efficient solution of free-surface
flows.” 2011. Web. 05 Mar 2021.
Vancouver:
Van den Bergh W. An algebraic
multigrid solution strategy for efficient solution of free-surface
flows. [Internet] [Masters thesis]. University of Pretoria; 2011. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/2263/28124.
Council of Science Editors:
Van den Bergh W. An algebraic
multigrid solution strategy for efficient solution of free-surface
flows. [Masters Thesis]. University of Pretoria; 2011. Available from: http://hdl.handle.net/2263/28124
8.
Pogulis, Markus.
Algebraic multigrid for a mass-consistent wind model, the Nordic Urban Dispersion model.
Degree: Physics, 2015, Umeå University
URL: http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-105499
► In preparation for, and for decision support during, CBRN (chemical, biological, radiological and nuclear) emergencies it is essential to know how such an event…
(more)
▼ In preparation for, and for decision support during, CBRN (chemical, biological, radiological and nuclear) emergencies it is essential to know how such an event would turn out, so that one can prepare a possible evacuation. Afterwards it might be good to know how to backtrack and see what caused the emergency, and in the case of e.g. a gas leak, where did it begin? The Swedish Defence Research Agency (FOI) develops models for such scenarios. In this thesis FOI's model, "The Nordic Urban Dispersion model" (NUD), has been studied. The system of equations set up by this model was originally solved using Intel's PARDISO solver, which is a direct solver. An evaluation on how an iterative multigrid method would work to solve the system has been done in this thesis. The wind model is a mass-consistent model which sets up a diagnostic initial wind field. The final wind field is later minimized under the constraint of the continuity equation. The minimization problem is solved using Lagrange multipliers and the system turns into a Poisson-like problem. The iterative algebraic multigrid solver (AMG) which has been evaluated had difficulties solving the problem of an asymmetric system matrix generated by NUD. The AMG solver was then tried on a symmetric discrete Poisson problem instead, and the solution turns out to be the same as for the PARDISO solver. A comparison was made between the AMG and PARDISO solver, and for the discrete Poisson case the AMG solver turned out on top for both larger system size and less computational time. To try out the solvers for the original NUD case a modification of the boundary conditions was made to make the system matrix symmetric. This modification turns the problem into a mathematical problem rather than a physical one, as the wind fields generated are not physically correct. For this modified case both the solvers get the same solution in essentially the same computational time. A method of how to in the future solve the original (asymmetric) problem, by modifying the discretization of the boundary conditions, has been discussed.
Subjects/Keywords: Mass-consistent model; urban environment; numerical method; algebraic multigrid
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Pogulis, M. (2015). Algebraic multigrid for a mass-consistent wind model, the Nordic Urban Dispersion model. (Thesis). Umeå University. Retrieved from http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-105499
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Pogulis, Markus. “Algebraic multigrid for a mass-consistent wind model, the Nordic Urban Dispersion model.” 2015. Thesis, Umeå University. Accessed March 05, 2021.
http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-105499.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Pogulis, Markus. “Algebraic multigrid for a mass-consistent wind model, the Nordic Urban Dispersion model.” 2015. Web. 05 Mar 2021.
Vancouver:
Pogulis M. Algebraic multigrid for a mass-consistent wind model, the Nordic Urban Dispersion model. [Internet] [Thesis]. Umeå University; 2015. [cited 2021 Mar 05].
Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-105499.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Pogulis M. Algebraic multigrid for a mass-consistent wind model, the Nordic Urban Dispersion model. [Thesis]. Umeå University; 2015. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-105499
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
9.
Junqueira, Luiz Antonio Custódio Manganelli.
Estudo de suavizadores para o método Multigrid algébrico baseado em wavelet.
Degree: Mestrado, Sistemas de Potência, 2008, University of São Paulo
URL: http://www.teses.usp.br/teses/disponiveis/3/3143/tde-18082008-141740/
;
► Este trabalho consiste na análise do comportamento do método WAMG (Wavelet-Based Algebraic Multigrid), método numérico de resolução de sistemas de equações lineares desenvolvido no LMAG-Laboratório…
(more)
▼ Este trabalho consiste na análise do comportamento do método WAMG (Wavelet-Based Algebraic Multigrid), método numérico de resolução de sistemas de equações lineares desenvolvido no LMAG-Laboratório de Eletromagnetismo Aplicado, com relação a diversos suavizadores. O fato dos vetores que compõem os operadores matriciais Pronlongamento e Restrição do método WAMG serem ortonormais viabiliza uma série de análises teóricas e de dados experimentais, permitindo visualizar características não permitidas nos outros métodos Multigrid (MG), englobando o Multigrid Geométrico (GMG) e o Multigrid Algébrico (AMG). O método WAMG V-Cycle com Filtro Haar é testado em uma variedade de sistemas de equações lineares variando o suavizador, o coeficiente de relaxação nos suavizadores Damped Jacobi e Sobre Relaxação Sucessiva (SOR), e a configuração de pré e pós-suavização. Entre os suavizadores testados, estão os métodos iterativos estacionários Damped Jacobi, SOR, Esparsa Aproximada a Inversa tipo Diagonal (SPAI-0) e métodos propostos com a característica de suavização para-otimizada. A título de comparação, métodos iterativos não estacionários são testados também como suavizadores como Gradientes Conjugados, Gradientes Bi-Conjugados e ICCG. Os resultados dos testes são apresentados e comentados.
This work is comprised of WAMG (Wavelet-Based Algebraic Multigrid) method behavioral analysis based on variety of smoothers, numerical method based on linear equation systems resolution developed at LMAG (Applied Electromagnetism Laboratory). Based on the fact that the vectors represented by WAMG Prolongation and Restriction matrix operators are orthonormals allows the use of a variety of theoretical and practical analysis, and therefore gain visibility of characteristics not feasible through others Multigrid (MG) methods, such as Geometric Multigrid (GMG) and Algebraic Multigrid (AMG). WAMG V-Cycle method with Haar Filter is tested under a variety of linear equation systems, by varying smoothers, relaxation coefficient at Damped Jacobi and Successive Over Relaxation (SOR) smoothers, and pre and post smoothers configurations. The tested smoothers are stationary iterative methods such as Damped Jacobi, SOR, Diagonal type-Sparse Approximate Inverse (SPAI-0) and suggested ones with optimized smoothing characteristic. For comparison purposes, the Conjugate Gradients, Bi-Conjugate Gradient and ICCG non-stationary iterative methods are also tested as smoothers. The testing results are formally presented and commented.
Advisors/Committee Members: Nabeta, Silvio Ikuyo.
Subjects/Keywords: Algebraic Multigrid; Finite elements method; Linear equations system; Método dos elementos finitos; Multigrid algébrico; Sistemas de equações lineares; Smoothers; Suavizadores
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Junqueira, L. A. C. M. (2008). Estudo de suavizadores para o método Multigrid algébrico baseado em wavelet. (Masters Thesis). University of São Paulo. Retrieved from http://www.teses.usp.br/teses/disponiveis/3/3143/tde-18082008-141740/ ;
Chicago Manual of Style (16th Edition):
Junqueira, Luiz Antonio Custódio Manganelli. “Estudo de suavizadores para o método Multigrid algébrico baseado em wavelet.” 2008. Masters Thesis, University of São Paulo. Accessed March 05, 2021.
http://www.teses.usp.br/teses/disponiveis/3/3143/tde-18082008-141740/ ;.
MLA Handbook (7th Edition):
Junqueira, Luiz Antonio Custódio Manganelli. “Estudo de suavizadores para o método Multigrid algébrico baseado em wavelet.” 2008. Web. 05 Mar 2021.
Vancouver:
Junqueira LACM. Estudo de suavizadores para o método Multigrid algébrico baseado em wavelet. [Internet] [Masters thesis]. University of São Paulo; 2008. [cited 2021 Mar 05].
Available from: http://www.teses.usp.br/teses/disponiveis/3/3143/tde-18082008-141740/ ;.
Council of Science Editors:
Junqueira LACM. Estudo de suavizadores para o método Multigrid algébrico baseado em wavelet. [Masters Thesis]. University of São Paulo; 2008. Available from: http://www.teses.usp.br/teses/disponiveis/3/3143/tde-18082008-141740/ ;
University of Colorado
10.
Fox, Alyson Lindsey.
Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.
Degree: PhD, Applied Mathematics, 2017, University of Colorado
URL: https://scholar.colorado.edu/appm_gradetds/96
► Relational datasets are often modeled as an unsigned, undirected graph due the nice properties of the resulting graph Laplacian, but information is lost if…
(more)
▼ Relational datasets are often modeled as an unsigned, undirected graph due the nice properties of the resulting graph Laplacian, but information is lost if certain attributes of the graph are not represented. This thesis presents two generalizations of
Algebraic Multigrid (AMG) solvers with graph Laplacian systems for different graph types: applying Gremban’s expansion to extend unsigned graph Laplacian solvers to signed graph Laplacian systems and generalizing techniques in Lean
Algebraic Multigrid (LAMG) to a new
multigrid solver for unsigned, directed graph Laplacian systems. Signed graphs extend the traditional notion of connections and disconnections to in- clude both favorable and adverse relationships, such as friend-enemy social networks or social networks with “likes” and “dislikes.” Gremban’s expansion is used to transform the signed graph Laplacian into an unsigned graph Laplacian with twice the number of unknowns. By using Gremban’s expansion, we extend current unsigned graph Laplacian solvers’ to signed graph Laplacians. This thesis analyzes the numerical stability and applicability of Grem- ban’s expansion and proves that the error of the solution of the original linear system can be tightly bounded by the error of the expanded system. In directed graphs, some subset of relationships are not reciprocal, such as hyperlink graphs, biological neural networks, and electrical power grids. A new
algebraic multigrid algorithm, Nonsymmetric Lean
Algebraic Multigrid (NS-LAMG), is proposed, which uses ideas from Lean
Algebraic Multigrid, nonsymmetric Smoothed Aggregation, and
multigrid solvers for Markov chain stationary distribution systems. Low-degree elimination, intro- duced in Lean
Algebraic Multigrid for undirected graphs, is redefined for directed graphs. A semi-adaptive
multigrid solver, inspired by low-degree elimination, is instrumented in the setup phase, which can be adapted for Markov chain stationary distributions systems. Nu- merical results shows that NS-LAMG out performs GMRES(k) for real-world, directed graph Laplacian linear systems. Both generalizations enable more choices in modeling decisions for graph Laplacian systems. Due the successfulness of NS-LAMG and other various nonsymmetric AMG (NS-AMG) solvers, a further study of theoretical convergence properties are discussed in this thesis. In particular, a necessary condition known as “weak approximation property”, and a sufficient one, referred to as “strong approximation property” as well as the “super strong approx- imation property” are generalized to nonsymmetric matrices and the various relationships between the approximation properties are proved for the nonsymmetric case. In NS-AMG, if P ̸= R the two-grid error propagation operator for the coarse-grid correction is an oblique projection with respect to any reasonable norm, which can cause the error to increase. A main focal point of this paper is a discussion on the conditions in which the error propagation operator is bounded, as the stability of the error…
Advisors/Committee Members: Tom Manteuffel, Geoff Sanders, John Ruge, Christian Ketelsen, Francois Meyer.
Subjects/Keywords: Algebraic Multigrid; Directed graphs; Graph Laplacians; Gremban's expansion; Signed graphs; Applied Mechanics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Fox, A. L. (2017). Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/96
Chicago Manual of Style (16th Edition):
Fox, Alyson Lindsey. “Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Doctoral Dissertation, University of Colorado. Accessed March 05, 2021.
https://scholar.colorado.edu/appm_gradetds/96.
MLA Handbook (7th Edition):
Fox, Alyson Lindsey. “Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs.” 2017. Web. 05 Mar 2021.
Vancouver:
Fox AL. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2021 Mar 05].
Available from: https://scholar.colorado.edu/appm_gradetds/96.
Council of Science Editors:
Fox AL. Algebraic Multigrid(amg) for Graph Laplacian Linear Systems: Extensions of Amg for Signed, Undirected and Unsigned, Directed Graphs. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/96
University of Colorado
11.
Southworth, Benjamin Scott.
Seeking Space Aliens and the Strong Approximation Property: a (Disjoint) Study in Dust Plumes on Planetary Satellites and Nonsymmetric Algebraic Multigrid.
Degree: PhD, Applied Mathematics, 2017, University of Colorado
URL: https://scholar.colorado.edu/appm_gradetds/99
► PART I: One of the most fascinating questions to humans has long been whether life exists outside of our planet. To our knowledge, water…
(more)
▼ PART I: One of the most fascinating questions to humans has long been whether life exists outside of our planet. To our knowledge, water is a fundamental building block of life, which makes liquid water on other bodies in the universe a topic of great interest. In fact, there are large bodies of water right here in our solar system, underneath the icy crust of moons around Saturn and Jupiter. The NASA-ESA Cassini Mission spent two decades studying the Saturnian system. One of the many exciting discoveries was a “plume” on the south pole of Enceladus, emitting hundreds of kg/s of water vapor and frozen water-ice particles from Enceladus’ subsurface ocean. It has since been determined that Enceladus likely has a global liquid water ocean separating its rocky core from icy surface, with conditions that are relatively favorable to support life. The plume is of particular interest because it gives direct access to ocean particles <i>from space</i>, by flying through the plume. Recently, evidence has been found for similar geological activity occurring on Jupiter’s moon Europa, long considered one of the most likely candidate bodies to support life in our solar system. Here, a model for plume-particle dynamics is developed based on studies of the Enceladus plume and data from the Cassini Cosmic Dust Analyzer. A C++, OpenMP/MPI parallel software package is then built to run large scale simulations of dust plumes on planetary satellites. In the case of Enceladus, data from simulations and the Cassini mission provide insight into the structure of emissions on the surface, the total mass production of the plume, and the distribution of particles being emitted. Each of these are fundamental to understanding the plume and, for Europa and Enceladus, simulation data provide important results for the planning of future missions to these icy moons. In particular, this work has contributed to the Europa Clipper mission and proposed Enceladus Life Finder. PART II: Solving large, sparse linear systems arises often in the modeling of biological and physical phenomenon, data analysis through graphs and networks, and other scientific applications. This work focuses primarily on linear systems resulting from the discretization of partial differential equations (PDEs). Because solving linear systems is the bottleneck of many large simulation codes, there is a rich field of research in developing “fast” solvers, with the ultimate goal being a method that solves an <i>n</i> × <i>n</i> linear system in O(<i>n</i>) operations. One of the most effective classes of solvers is
algebraic multigrid (AMG), which is a multilevel iterative method based on projecting the problem into progressively smaller spaces, and scales like O(<i>n</i>) or O(<i>n</i>log<i>n</i>) for certain classes of problems. The field of AMG is well-developed for symmetric positive definite matrices, and is typically most effective on linear systems resulting from the discretization of scalar elliptic PDEs, such as the heat equation. Systems of PDEs can add…
Advisors/Committee Members: Thomas A. Manteuffel, Sascha Kempf, Steve McCormick, John Ruge, Jacob Schroder.
Subjects/Keywords: algebraic multigrid; dust plume; Enceladus; linear system; nonsymmetric; transport; Applied Mathematics; Physics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Southworth, B. S. (2017). Seeking Space Aliens and the Strong Approximation Property: a (Disjoint) Study in Dust Plumes on Planetary Satellites and Nonsymmetric Algebraic Multigrid. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/99
Chicago Manual of Style (16th Edition):
Southworth, Benjamin Scott. “Seeking Space Aliens and the Strong Approximation Property: a (Disjoint) Study in Dust Plumes on Planetary Satellites and Nonsymmetric Algebraic Multigrid.” 2017. Doctoral Dissertation, University of Colorado. Accessed March 05, 2021.
https://scholar.colorado.edu/appm_gradetds/99.
MLA Handbook (7th Edition):
Southworth, Benjamin Scott. “Seeking Space Aliens and the Strong Approximation Property: a (Disjoint) Study in Dust Plumes on Planetary Satellites and Nonsymmetric Algebraic Multigrid.” 2017. Web. 05 Mar 2021.
Vancouver:
Southworth BS. Seeking Space Aliens and the Strong Approximation Property: a (Disjoint) Study in Dust Plumes on Planetary Satellites and Nonsymmetric Algebraic Multigrid. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2021 Mar 05].
Available from: https://scholar.colorado.edu/appm_gradetds/99.
Council of Science Editors:
Southworth BS. Seeking Space Aliens and the Strong Approximation Property: a (Disjoint) Study in Dust Plumes on Planetary Satellites and Nonsymmetric Algebraic Multigrid. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/99
12.
Miller, Killian.
Algebraic Multigrid for Markov Chains and Tensor Decomposition.
Degree: 2013, University of Waterloo
URL: http://hdl.handle.net/10012/7234
► The majority of this thesis is concerned with the development of efficient and robust numerical methods based on adaptive algebraic multigrid to compute the stationary…
(more)
▼ The majority of this thesis is concerned with the development of efficient and robust numerical methods based on adaptive algebraic multigrid to compute the stationary distribution of Markov chains. It is shown that classical algebraic multigrid techniques can be applied in an exact interpolation scheme framework to compute the stationary distribution of irreducible, homogeneous Markov chains. A quantitative analysis shows that algebraically smooth multiplicative error is locally constant along strong connections in a scaled system operator, which suggests that classical algebraic multigrid coarsening and interpolation can be applied to the class of nonsymmetric irreducible singular M-matrices with zero column sums. Acceleration schemes based on fine-level iterant recombination, and over-correction of the coarse-grid correction are developed to improve the rate of convergence and scalability of simple adaptive aggregation multigrid methods for Markov chains. Numerical tests over a wide range of challenging nonsymmetric test problems demonstrate the effectiveness of the proposed multilevel method and the acceleration schemes.
This thesis also investigates the application of adaptive algebraic multigrid techniques for computing the canonical decomposition of higher-order tensors. The canonical decomposition is formulated as a least squares optimization problem, for which local minimizers are computed by solving the first-order optimality equations. The proposed multilevel method consists of two phases: an adaptive setup phase that uses a multiplicative correction scheme in conjunction with bootstrap algebraic multigrid interpolation to build the necessary operators on each level, and a solve phase that uses additive correction cycles based on the full approximation scheme to efficiently obtain an accurate solution. The alternating least squares method, which is a standard one-level iterative method for computing the canonical decomposition, is used as the relaxation scheme. Numerical tests show that for certain test problems arising from the discretization of high-dimensional partial differential equations on regular lattices the proposed multilevel method significantly outperforms the standard alternating least squares method when a high level of accuracy is required.
Subjects/Keywords: multigrid; algebraic multigrid; Markov chain; stationary distribution; tensor; canonical decomposition
…methods based on
adaptive algebraic multigrid (AMG) for solving problems in linear and… …advances having only
recently been made [31, 96].
4
1.2
Algebraic multigrid for… …multiplicative correction scheme in conjunction with bootstrap algebraic multigrid (BAMG)… …framework we propose is closely related to recent work
on an adaptive algebraic multigrid method… …F. McCormick, K. Miller, J. W. Ruge, and
G. Sanders. Algebraic multigrid for Markov chains…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Miller, K. (2013). Algebraic Multigrid for Markov Chains and Tensor Decomposition. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/7234
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Miller, Killian. “Algebraic Multigrid for Markov Chains and Tensor Decomposition.” 2013. Thesis, University of Waterloo. Accessed March 05, 2021.
http://hdl.handle.net/10012/7234.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Miller, Killian. “Algebraic Multigrid for Markov Chains and Tensor Decomposition.” 2013. Web. 05 Mar 2021.
Vancouver:
Miller K. Algebraic Multigrid for Markov Chains and Tensor Decomposition. [Internet] [Thesis]. University of Waterloo; 2013. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/10012/7234.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Miller K. Algebraic Multigrid for Markov Chains and Tensor Decomposition. [Thesis]. University of Waterloo; 2013. Available from: http://hdl.handle.net/10012/7234
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Colorado
13.
Mitchell, Wayne Bradford.
Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.
Degree: PhD, 2017, University of Colorado
URL: https://scholar.colorado.edu/appm_gradetds/126
► When solving elliptic partial differential equations (PDE's) multigrid algorithms often provide optimal solvers and preconditioners capable of providing solutions with <i>O</i>(<i>N</i>) computational cost, where…
(more)
▼ When solving elliptic partial differential equations (PDE's)
multigrid algorithms often provide optimal solvers and preconditioners capable of providing solutions with <i>O</i>(<i>N</i>) computational cost, where <i>N</i> is the number of unknowns. As parallelism of modern super computers continues to grow towards exascale, however, the cost of communication has overshadowed the cost of computation as the next major bottleneck for
multigrid algorithms. Typically,
multigrid algorithms require <i>O</i>((log <i>P</i>)
2) communication steps in order to solve a PDE problem to the level of discretization accuracy, where <i>P</i> is the number of processors. This has inspired the development of new algorithms that employ novel paradigms for parallelizing PDE problems, and this thesis studies and further develops two such algorithms. The nested iteration with range decomposition (NIRD) algorithm is known to achieve accuracy similar to that of traditional methods in only a single iteration with log <i>P</i> communication steps for simple elliptic problems. This thesis makes several improvements to the NIRD algorithm and extends its application to a much wider variety of problems, while also examining and updating previously proposed convergence theory and performance models. The second method studied is the
algebraic multigrid with domain decomposition (AMG-DD) algorithm. Though previous work showed only marginal benefits when comparing convergence factors for AMG-DD against standard AMG V-cycles, this thesis studies the potential of AMG-DD as a discretization-accuracy solver. In addition to detailing the first parallel implementation of this algorithm, this thesis also shows new results that study the effect of different AMG coarsening and interpolation strategies on AMG-DD convergence and show some evidence to suggest AMG-DD may achieve discretization accuracy in a fixed number of cycles with <i>O</i>(log <i>P</i>) communication cost even as problem size increases.
Advisors/Committee Members: Thomas A. Manteuffel, Stephen F. McCormick, John Ruge.
Subjects/Keywords: adaptive mesh refinement; algebraic multigrid; domain decomposition; first-order system least-squares; nested iteration; range decomposition; Applied Mathematics; Partial Differential Equations
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mitchell, W. B. (2017). Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/126
Chicago Manual of Style (16th Edition):
Mitchell, Wayne Bradford. “Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.” 2017. Doctoral Dissertation, University of Colorado. Accessed March 05, 2021.
https://scholar.colorado.edu/appm_gradetds/126.
MLA Handbook (7th Edition):
Mitchell, Wayne Bradford. “Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.” 2017. Web. 05 Mar 2021.
Vancouver:
Mitchell WB. Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2021 Mar 05].
Available from: https://scholar.colorado.edu/appm_gradetds/126.
Council of Science Editors:
Mitchell WB. Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/126
14.
Li, Jizhou.
High order discontinuous Galerkin methods for simulating miscible displacement process in porous media with a focus on minimal regularity.
Degree: PhD, Engineering, 2015, Rice University
URL: http://hdl.handle.net/1911/88087
► In my thesis, I formulate, analyze and implement high order discontinuous Galerkin methods for simulating miscible displacement in porous media. The analysis concerning the stability…
(more)
▼ In my thesis, I formulate, analyze and implement high order discontinuous Galerkin methods for simulating miscible displacement in porous media. The analysis concerning the stability and convergence under the minimal regularity assumption is established to provide theoretical foundations for using discontinuous Galerkin discretization to solve miscible displacement problems. The numerical experiments demonstrate the robustness and accuracy of the proposed methods. The performance study for large scale simulations with highly heterogeneous porous media suggests strong scalability which indicates the efficiency of the numerical algorithm. The simulations performed using the algorithms for physically unstable flow show that higher order methods proposed in thesis are more suitable for simulating such phenomenon than the commonly used cell-center finite volume method.
Advisors/Committee Members: Riviere, Beatrice M. (advisor), Symes, William (committee member), Hirasaki, George (committee member), Warburton, Timothy (committee member), Heinkenschloss, Matthias (committee member).
Subjects/Keywords: discontinuous Galerkin methods; miscible displacement; reservoir simulations; high performance computing; high order methods; viscous fingering; algebraic multigrid; domain decomposition
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Li, J. (2015). High order discontinuous Galerkin methods for simulating miscible displacement process in porous media with a focus on minimal regularity. (Doctoral Dissertation). Rice University. Retrieved from http://hdl.handle.net/1911/88087
Chicago Manual of Style (16th Edition):
Li, Jizhou. “High order discontinuous Galerkin methods for simulating miscible displacement process in porous media with a focus on minimal regularity.” 2015. Doctoral Dissertation, Rice University. Accessed March 05, 2021.
http://hdl.handle.net/1911/88087.
MLA Handbook (7th Edition):
Li, Jizhou. “High order discontinuous Galerkin methods for simulating miscible displacement process in porous media with a focus on minimal regularity.” 2015. Web. 05 Mar 2021.
Vancouver:
Li J. High order discontinuous Galerkin methods for simulating miscible displacement process in porous media with a focus on minimal regularity. [Internet] [Doctoral dissertation]. Rice University; 2015. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/1911/88087.
Council of Science Editors:
Li J. High order discontinuous Galerkin methods for simulating miscible displacement process in porous media with a focus on minimal regularity. [Doctoral Dissertation]. Rice University; 2015. Available from: http://hdl.handle.net/1911/88087
15.
Howse, Alexander James Maxwell.
Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations.
Degree: 2017, University of Waterloo
URL: http://hdl.handle.net/10012/12559
► This thesis consists of two main parts, part one addressing problems from nonlinear optimization and part two based on solving systems of time dependent differential…
(more)
▼ This thesis consists of two main parts, part one addressing problems from nonlinear optimization and part two based on solving systems of time dependent differential equations, with both parts describing strategies for accelerating the convergence of iterative methods.
In part one we present a nonlinear preconditioning framework for use with nonlinear solvers applied to nonlinear optimization problems, motivated by a generalization of linear left preconditioning and linear preconditioning via a change of variables for minimizing quadratic objective functions. In the optimization context nonlinear preconditioning is used to generate a preconditioner direction that either replaces or supplements the gradient vector throughout the optimization algorithm. This framework is used to discuss previously developed nonlinearly preconditioned nonlinear GMRES and nonlinear conjugate gradients (NCG) algorithms, as well as to develop two new nonlinearly preconditioned quasi-Newton methods based on the limited memory Broyden and limited memory BFGS (L-BFGS) updates. We show how all of the above methods can be implemented in a manifold optimization context, with a particular emphasis on Grassmann matrix manifolds.
These methods are compared by solving the optimization problems defining the canonical polyadic (CP) decomposition and Tucker higher order singular value decomposition (HOSVD) for tensors, which are formulated as minimizing approximation error in the Frobenius norm. Both of these decompositions have alternating least squares (ALS) type fixed point iterations derived from their optimization problem definitions. While these ALS type iterations may be slow to converge in practice, they can serve as efficient nonlinear preconditioners for the other optimization methods. As the Tucker HOSVD problem involves orthonormality constraints and lacks unique minimizers, the optimization algorithms are extended from Euclidean space to the manifold setting, where optimization on Grassmann manifolds can resolve both of the issues present in the HOSVD problem.
The nonlinearly preconditioned methods are compared to the ALS type preconditioners and non-preconditioned NCG, L-BFGS, and a trust region algorithm using both synthetic and real life tensor data with varying noise level, the real data arising from applications in computer vision and handwritten digit recognition. Numerical results show that the nonlinearly preconditioned methods offer substantial improvements in terms of time-to-solution and robustness over state-of-the-art methods for large tensors, in cases where there are significant amounts of noise in the data, and when high accuracy results are required.
In part two we apply a multigrid reduction-in-time (MGRIT) algorithm to scalar one-dimensional hyperbolic partial differential equations. This study is motivated by the observation that sequential time-stepping is an obvious computational bottleneck when attempting to implement highly concurrent algorithms, thus parallel-in-time methods are particularly…
Subjects/Keywords: Nonlinear Preconditioning; Nonlinear Optimization; Quasi-Newton Methods; Tensor Decomposition; CP Tensor; Tucker Tensor; Parallel-in-Time Integration; Multigrid Reduction-in-Time; MGRIT; Hyperbolic Partial Differential Equations; Variable Coefficient Linear Advection; Burgers' Equation; Multigrid; Adaptive Grid Coarsening; Waveform Relaxation Multigrid; Semi-Algebraic Mode Analysis
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Howse, A. J. M. (2017). Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/12559
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Howse, Alexander James Maxwell. “Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations.” 2017. Thesis, University of Waterloo. Accessed March 05, 2021.
http://hdl.handle.net/10012/12559.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Howse, Alexander James Maxwell. “Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations.” 2017. Web. 05 Mar 2021.
Vancouver:
Howse AJM. Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations. [Internet] [Thesis]. University of Waterloo; 2017. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/10012/12559.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Howse AJM. Nonlinear Preconditioning Methods for Optimization and Parallel-In-Time Methods for 1D Scalar Hyperbolic Partial Differential Equations. [Thesis]. University of Waterloo; 2017. Available from: http://hdl.handle.net/10012/12559
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Brigham Young University
16.
Larson, Gregory James.
Performance of Algebraic Multigrid for Parallelized Finite Element DNS/LES Solvers.
Degree: MS, 2006, Brigham Young University
URL: https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1783&context=etd
► The implementation of a hybrid spectral/finite-element discretization on the unsteady, incompressible, Navier-Stokes equations with a semi-implicit time-stepping method, an explicit treatment of the advective terms,…
(more)
▼ The implementation of a hybrid spectral/finite-element discretization on the unsteady, incompressible, Navier-Stokes equations with a semi-implicit time-stepping method, an explicit treatment of the advective terms, and an implicit treatment of the pressure and viscous terms leads to an algorithm capable of calculating 3D flows over complex 2D geometries. This also results in multiple Fourier mode linear systems which must be solved at every timestep, which naturally leads to two parallelization approaches: Fourier space partitioning, where each processor individually and simultaneously solves a linear system, and physical space partitioning, where all processors collectively solve each linear system, sequentially advancing through Fourier modes. These two parallelization approaches are compared based upon computational cost using multiple solvers: direct sparse LU, smoothed aggregation AMG, and single-level ILUT preconditioned GMRES; and on two supercomputers of different memory architecture(distributed and shared memory). This study revealed Fourier space partitioning outperforms physical space partitioning in all problems analyzed, and scales more efficiently as well. These differences were more dramatic on the distributed memory platform than the shared memory platform. Another study compares the previously mentioned solvers along with one additional solver, pointwise AMG, in Fourier space partitioning without parallelization to better understand computational scaling for problems with large meshes. It was found that the direct sparse LU solver performed well in terms of computational time, scaled linearly, but had very high memory usage which scaled in a super-linear manner. The single-level ILUT preconditioned GMRES solver required the least amount of memory, which also scaled linearly, but only had acceptable performance in terms of computational time for coarse meshes. Both AMG methods scaled linearly in both memory usage and time, and were comparable to the direct sparse LU solver in terms of computational time. The results of these studies are particularly useful for implementation of this algorithm on challenging and complex flows, especially direct numerical and large-eddy simulations. Reducing computational cost allows the analysis and understanding of more flows of practical interest.
Subjects/Keywords: algebraic multigrid; Navier-Stokes equations; large eddy simulation; direct numerical simulation; Mechanical Engineering
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Larson, G. J. (2006). Performance of Algebraic Multigrid for Parallelized Finite Element DNS/LES Solvers. (Masters Thesis). Brigham Young University. Retrieved from https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1783&context=etd
Chicago Manual of Style (16th Edition):
Larson, Gregory James. “Performance of Algebraic Multigrid for Parallelized Finite Element DNS/LES Solvers.” 2006. Masters Thesis, Brigham Young University. Accessed March 05, 2021.
https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1783&context=etd.
MLA Handbook (7th Edition):
Larson, Gregory James. “Performance of Algebraic Multigrid for Parallelized Finite Element DNS/LES Solvers.” 2006. Web. 05 Mar 2021.
Vancouver:
Larson GJ. Performance of Algebraic Multigrid for Parallelized Finite Element DNS/LES Solvers. [Internet] [Masters thesis]. Brigham Young University; 2006. [cited 2021 Mar 05].
Available from: https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1783&context=etd.
Council of Science Editors:
Larson GJ. Performance of Algebraic Multigrid for Parallelized Finite Element DNS/LES Solvers. [Masters Thesis]. Brigham Young University; 2006. Available from: https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1783&context=etd
University of Colorado
17.
Mitchell, Wayne.
Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.
Degree: PhD, Applied Mathematics, 2017, University of Colorado
URL: https://scholar.colorado.edu/appm_gradetds/80
► When solving elliptic partial differential equations (PDE's) multigrid algorithms often provide optimal solvers and preconditioners capable of providing solutions with O(N) computational cost, where…
(more)
▼ When solving elliptic partial differential equations (PDE's)
multigrid algorithms often provide optimal solvers and preconditioners capable of providing solutions with O(N) computational cost, where N is the number of unknowns. As parallelism of modern super computers continues to grow towards exascale, however, the cost of communication has overshadowed the cost of computation as the next major bottleneck for
multigrid algorithms. Typically,
multigrid algorithms require O((log P)
2) communication steps in order to solve a PDE problem to the level of discretization accuracy, where P is the number of processors. This has inspired the development of new algorithms that employ novel paradigms for parallelizing PDE problems, and this thesis studies and further develops two such algorithms.
The nested iteration with range decomposition (NIRD) algorithm is known to achieve accuracy similar to that of traditional methods in only a single iteration with log P communication steps for simple elliptic problems. This thesis makes several improvements to the NIRD algorithm and extends its application to a much wider variety of problems, while also examining and updating previously proposed convergence theory and performance models.
The second method studied is the
algebraic multigrid with domain decomposition (AMG-DD) algorithm. Though previous work showed only marginal benefits when comparing convergence factors for AMG-DD against standard AMG V-cycles, this thesis studies the potential of AMG-DD as a discretization-accuracy solver. In addition to detailing the first parallel implementation of this algorithm, this thesis also shows new results that study the effect of different AMG coarsening and interpolation strategies on AMG-DD convergence and show some evidence to suggest AMG-DD may achieve discretization accuracy in a fixed number of cycles with O(log P) communication cost even as problem size increases.
Advisors/Committee Members: Thomas A. Manteuffel, Stephen F. McCormick.
Subjects/Keywords: nested iteration; first-order system least-squares; algebraic multigrid; domain decomposition; range decomposition; adaptive mesh refinement; Applied Mathematics; Numerical Analysis and Computation; Partial Differential Equations
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mitchell, W. (2017). Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/80
Chicago Manual of Style (16th Edition):
Mitchell, Wayne. “Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.” 2017. Doctoral Dissertation, University of Colorado. Accessed March 05, 2021.
https://scholar.colorado.edu/appm_gradetds/80.
MLA Handbook (7th Edition):
Mitchell, Wayne. “Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations.” 2017. Web. 05 Mar 2021.
Vancouver:
Mitchell W. Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. [Internet] [Doctoral dissertation]. University of Colorado; 2017. [cited 2021 Mar 05].
Available from: https://scholar.colorado.edu/appm_gradetds/80.
Council of Science Editors:
Mitchell W. Low-Communication, Parallel Multigrid Algorithms for Elliptic Partial Differential Equations. [Doctoral Dissertation]. University of Colorado; 2017. Available from: https://scholar.colorado.edu/appm_gradetds/80
Delft University of Technology
18.
Abdoel, S.M.F. (author).
Solution of the vector wave equation using a Krylov solver with an algebraic multigrid approximated preconditioner.
Degree: Electrical Engineering, Mathematics and Computer Science, Applied Mathematics, 2008, Delft University of Technology
URL: http://resolver.tudelft.nl/uuid:decbefca-9448-47da-9b8c-cce9a0098062
Electrical Engineering, Mathematics and Computer Science
Advisors/Committee Members: Vuik, C. (mentor), Van der Heul, D. (mentor).Subjects/Keywords: radar; rcs; large sparse systems; iterative methods; algebraic multigrid preconditioning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Abdoel, S. M. F. (. (2008). Solution of the vector wave equation using a Krylov solver with an algebraic multigrid approximated preconditioner. (Masters Thesis). Delft University of Technology. Retrieved from http://resolver.tudelft.nl/uuid:decbefca-9448-47da-9b8c-cce9a0098062
Chicago Manual of Style (16th Edition):
Abdoel, S M F (author). “Solution of the vector wave equation using a Krylov solver with an algebraic multigrid approximated preconditioner.” 2008. Masters Thesis, Delft University of Technology. Accessed March 05, 2021.
http://resolver.tudelft.nl/uuid:decbefca-9448-47da-9b8c-cce9a0098062.
MLA Handbook (7th Edition):
Abdoel, S M F (author). “Solution of the vector wave equation using a Krylov solver with an algebraic multigrid approximated preconditioner.” 2008. Web. 05 Mar 2021.
Vancouver:
Abdoel SMF(. Solution of the vector wave equation using a Krylov solver with an algebraic multigrid approximated preconditioner. [Internet] [Masters thesis]. Delft University of Technology; 2008. [cited 2021 Mar 05].
Available from: http://resolver.tudelft.nl/uuid:decbefca-9448-47da-9b8c-cce9a0098062.
Council of Science Editors:
Abdoel SMF(. Solution of the vector wave equation using a Krylov solver with an algebraic multigrid approximated preconditioner. [Masters Thesis]. Delft University of Technology; 2008. Available from: http://resolver.tudelft.nl/uuid:decbefca-9448-47da-9b8c-cce9a0098062
19.
Dalton, Steven.
Data parallel algebraic multigrid.
Degree: PhD, 0112, 2015, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/72802
► Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks…
(more)
▼ Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks suitable for distributed computers with traditional processing cores. Accelerating
multigrid methods on massively parallel throughput-oriented processors, on the other hand, demands algorithms with abundant fine-grained parallelism. In this dissertation we analyze and decompose the smoothed aggregation
algebraic multigrid method into parallel primitives effectively mapped to emerging architectures. Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix multiplication. In the second phase, we address this performance bottleneck using novel techniques to optimize irregular sparse matrix operations.
This dissertation is also concerned with irregular graph operations necessary to partition sparse matrices into disjoint sets for parallel processing. We apply our solver to accelerate eigenvector computations necessary during spectral partitioning methods and find that performance is limited by
multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely
blocked Lanczos, with breadth first search operations on graphs. By basing our partitioner on primitives with substantial parallelism we demonstrate notable performance improvement compared with generic eigensolvers.
Advisors/Committee Members: Olson, Luke (advisor), Olson, Luke (Committee Chair), Gropp, William (committee member), Heath, Michael (committee member), Brown, Jed (committee member).
Subjects/Keywords: graphics processing unit (GPU); algebraic multigrid (AMG); Sparse matrix
…families: geometric and algebraic. Geometric multigrid
(GMG) methods were the earliest… …geometry limits the general applicability. To address this limitation algebraic multigrid (… …Lanczos methods.
5
Chapter 2
Algebraic Multigrid
Multigrid methods precondition large… …through the
geometry and physics of the problem. In contrast, algebraic-based multigrid methods… …multigrid are plentiful. Algebraic multigrid methods have been successfully parallelized on…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Dalton, S. (2015). Data parallel algebraic multigrid. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/72802
Chicago Manual of Style (16th Edition):
Dalton, Steven. “Data parallel algebraic multigrid.” 2015. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 05, 2021.
http://hdl.handle.net/2142/72802.
MLA Handbook (7th Edition):
Dalton, Steven. “Data parallel algebraic multigrid.” 2015. Web. 05 Mar 2021.
Vancouver:
Dalton S. Data parallel algebraic multigrid. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2015. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/2142/72802.
Council of Science Editors:
Dalton S. Data parallel algebraic multigrid. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2015. Available from: http://hdl.handle.net/2142/72802
20.
Garcia Hilares, Nilton Alan.
A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid.
Degree: MS, Mathematics, 2019, Virginia Tech
URL: http://hdl.handle.net/10919/94618
► Modeling real-world problems incurs a high computational cost because these mathematical models involve large-scale data manipulation. Thus we need fast and efficient algorithms. Nowadays there…
(more)
▼ Modeling real-world problems incurs a high computational cost because these mathematical models involve large-scale data manipulation. Thus we need fast and efficient algorithms. Nowadays there are many high-performance approaches for these problems.
One such method is called the
Multigrid algorithm. This approach models a physical domain using a hierarchy of grids, and so the effectiveness of these approaches relies on how well data can be transferred from grid to grid. In this thesis, we focus on the aggregation approach, which clusters a grid’s vertices according to its connections. We also provide an alternative parallel aggregation algorithm to give a faster solution. We show numerous experimental results that compare different aggregation approaches and
multigrid methods, showing that our proposed algorithm performs better in serial and parallel than other popular
implementations.
Advisors/Committee Members: Embree, Mark P. (committeechair), De Sturler, Eric (committee member), Warburton, Timothy (committee member).
Subjects/Keywords: Algebraic multigrid; Aggregation; Maximal independent set; Poisson's equation
…methods to solve scientific and engineering problems in real time. Algebraic Multigrid (AMG… …we use an alternative approach called algebraic multigrid.
This technique can be seen as a… …the effectiveness of algebraic multigrid algorithms depends on the inter-grid transfer… …computational results of our experiments. Here we start comparing algebraic multigrid as a solver and… …x28;as grids), so R can be the canonical
injection, but in the Algebraic Multigrid…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Garcia Hilares, N. A. (2019). A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid. (Masters Thesis). Virginia Tech. Retrieved from http://hdl.handle.net/10919/94618
Chicago Manual of Style (16th Edition):
Garcia Hilares, Nilton Alan. “A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid.” 2019. Masters Thesis, Virginia Tech. Accessed March 05, 2021.
http://hdl.handle.net/10919/94618.
MLA Handbook (7th Edition):
Garcia Hilares, Nilton Alan. “A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid.” 2019. Web. 05 Mar 2021.
Vancouver:
Garcia Hilares NA. A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid. [Internet] [Masters thesis]. Virginia Tech; 2019. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/10919/94618.
Council of Science Editors:
Garcia Hilares NA. A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid. [Masters Thesis]. Virginia Tech; 2019. Available from: http://hdl.handle.net/10919/94618
Arizona State University
21.
Guo, Xinchen.
Algebraic Multigrid Poisson Equation Solver.
Degree: Materials Science and Engineering, 2015, Arizona State University
URL: http://repository.asu.edu/items/29693
Subjects/Keywords: Electrical engineering; Applied mathematics; Computer science; Algebraic; Device simulator; Multigrid; Poisson Equation
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Guo, X. (2015). Algebraic Multigrid Poisson Equation Solver. (Masters Thesis). Arizona State University. Retrieved from http://repository.asu.edu/items/29693
Chicago Manual of Style (16th Edition):
Guo, Xinchen. “Algebraic Multigrid Poisson Equation Solver.” 2015. Masters Thesis, Arizona State University. Accessed March 05, 2021.
http://repository.asu.edu/items/29693.
MLA Handbook (7th Edition):
Guo, Xinchen. “Algebraic Multigrid Poisson Equation Solver.” 2015. Web. 05 Mar 2021.
Vancouver:
Guo X. Algebraic Multigrid Poisson Equation Solver. [Internet] [Masters thesis]. Arizona State University; 2015. [cited 2021 Mar 05].
Available from: http://repository.asu.edu/items/29693.
Council of Science Editors:
Guo X. Algebraic Multigrid Poisson Equation Solver. [Masters Thesis]. Arizona State University; 2015. Available from: http://repository.asu.edu/items/29693
Michigan Technological University
22.
Zhao, Zhiqiang.
HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS.
Degree: PhD, Department of Electrical and Computer Engineering, 2020, Michigan Technological University
URL: https://digitalcommons.mtu.edu/etdr/1138
► Recent research shows that by leveraging the key spectral properties of eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for…
(more)
▼ Recent research shows that by leveraging the key spectral properties of eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for tackling many graph-related computing tasks. In this dissertation, spectral methods are utilized for achieving faster algorithms in the applications of very-large-scale integration (VLSI) computer-aided design (CAD)
First, a scalable algorithmic framework is proposed for effective-resistance preserving spectral reduction of large undirected graphs. The proposed method allows computing much smaller graphs while preserving the key spectral (structural) properties of the original graph. Our framework is built upon the following three key components: a spectrum-preserving node aggregation and reduction scheme, a spectral graph sparsification framework with iterative edge weight scaling, as well as effective-resistance preserving post-scaling and iterative solution refinement schemes. We show that the resultant spectrally-reduced graphs can robustly preserve the first few nontrivial eigenvalues and eigenvectors of the original graph Laplacian and thus allow for developing highly-scalable spectral graph partitioning and circuit simulation algorithms.
Based on the framework of the spectral graph reduction, a Sparsified graph-theoretic
Algebraic Multigrid (SAMG) is proposed for solving large Symmetric Diagonally Dominant (SDD) matrices. The proposed SAMG framework allows efficient construction of nearly-linear sized graph Laplacians for coarse-level problems while maintaining good spectral approximation during the AMG setup phase by leveraging a scalable spectral graph sparsification engine. Our experimental results show that the proposed method can offer more scalable performance than existing graph-theoretic AMG solvers for solving large SDD matrices in integrated circuit (IC) simulations, 3D-IC thermal analysis, image processing, finite element analysis as well as data mining and machine learning applications.
Finally, the spectral methods are applied to power grid and thermal integrity verification applications. This dissertation introduces a vectorless power grid and thermal integrity verification framework that allows computing worst-case voltage drop or thermal profiles across the entire chip under a set of local and global workload (power density) constraints. To address the computational challenges introduced by the large 3D mesh-structured thermal grids, we apply the spectral graph reduction approach for highly-scalable vectorless thermal (or power grids) verification of large chip designs. The effectiveness and efficiency of our approach have been demonstrated through extensive experiments.
Advisors/Committee Members: Zhuo Feng, Glen E. Archer.
Subjects/Keywords: Spectral graph theory; computer-aided design; spectral sparsification; spectral graph reduction; algebraic multigrid; vectorless verification; Other Computer Engineering; VLSI and Circuits, Embedded and Hardware Systems
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Zhao, Z. (2020). HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS. (Doctoral Dissertation). Michigan Technological University. Retrieved from https://digitalcommons.mtu.edu/etdr/1138
Chicago Manual of Style (16th Edition):
Zhao, Zhiqiang. “HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS.” 2020. Doctoral Dissertation, Michigan Technological University. Accessed March 05, 2021.
https://digitalcommons.mtu.edu/etdr/1138.
MLA Handbook (7th Edition):
Zhao, Zhiqiang. “HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS.” 2020. Web. 05 Mar 2021.
Vancouver:
Zhao Z. HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS. [Internet] [Doctoral dissertation]. Michigan Technological University; 2020. [cited 2021 Mar 05].
Available from: https://digitalcommons.mtu.edu/etdr/1138.
Council of Science Editors:
Zhao Z. HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS. [Doctoral Dissertation]. Michigan Technological University; 2020. Available from: https://digitalcommons.mtu.edu/etdr/1138
University of Illinois – Urbana-Champaign
23.
Schroder, Jacob B.
Generalizing smoothed aggregation-based algebraic multigrid.
Degree: PhD, 0112, 2010, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/17044
► Smoothed aggregation-based (SA) algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While…
(more)
▼ Smoothed aggregation-based (SA)
algebraic multigrid (AMG) is a popular and
effective solver for systems of linear equations that arise from discretized
partial differential equations. While SA has been effective over a broad class
of problems, it has several limitations and weaknesses that this thesis is
intended to address. This includes the development of a more robust
strength-of-connection measure which guides coarsening and the
choice of interpolation sparsity patterns. Unfortunately, the classic strength
measure is only well-founded for M-matrices, leading us to develop a new
measure based on local knowledge of both algebraically smooth error and the
behavior of interpolation. Another limitation is that classic SA is only formally
defined for Hermitian positive definite problems. For non-Hermitian
operators, the operator-induced energy-norm does not exist, which impacts the
complementary relationship between relaxation and interpolation. This requires
a redesign of SA, such that restriction and prolongation operators approximate
the left and right near null-spaces, respectively. As a result, we develop general SA
setup algorithms for both the Hermitian positive-definite and the non-Hermitian
cases. To realize these algorithms, we develop general prolongation smoothing
methods so that restriction and prolongation target the left and right near null-spaces,
respectively. Overall, the proposed methods do not assume any user-input
beyond what standard SA does and the result is a new direction for
multigrid
methods for non-Hermitian systems. Several problem areas motivate our
development. For example, rotated anisotropic diffusion and linearized
elasticity problems using standard discretizations can easily generate
non-M-matrices that prove difficult for standard SA and AMG. High- and
low-order discontinuous Galerkin discretizations also generate difficult non-M-matrices for elliptic
problems. Target non-Hermitian problems include flow problems and
wave-like problems, e.g., Helmholtz. Additionally for wave-like
problems, there is a rich non-standard wave-like near null-space, which must be captured
by the coarse levels???a task beyond the scope of traditional AMG
or SA coarsening techniques.
Advisors/Committee Members: Olson, Luke N. (advisor), Olson, Luke N. (Committee Chair), Gropp, William D. (committee member), Heath, Michael T. (committee member), Tuminaro, Raymond S. (committee member).
Subjects/Keywords: smoothed aggregation; algebraic multigrid; Helmholtz; indefinite; nonsymmetric; algebraic coarsening; discontinuous Galerkin; high-order; prolongation smoothing; strength-of-connection
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Schroder, J. B. (2010). Generalizing smoothed aggregation-based algebraic multigrid. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/17044
Chicago Manual of Style (16th Edition):
Schroder, Jacob B. “Generalizing smoothed aggregation-based algebraic multigrid.” 2010. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 05, 2021.
http://hdl.handle.net/2142/17044.
MLA Handbook (7th Edition):
Schroder, Jacob B. “Generalizing smoothed aggregation-based algebraic multigrid.” 2010. Web. 05 Mar 2021.
Vancouver:
Schroder JB. Generalizing smoothed aggregation-based algebraic multigrid. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2010. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/2142/17044.
Council of Science Editors:
Schroder JB. Generalizing smoothed aggregation-based algebraic multigrid. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2010. Available from: http://hdl.handle.net/2142/17044
24.
Klonk, Steffen.
Modélisation numérique du chauffage par induction de pièces à géométrie complexe : Numerical modelling of induction heating for complex geometrical parts.
Degree: Docteur es, Mécanique numérique, 2013, Paris, ENMP
URL: http://www.theses.fr/2013ENMP0077
► Le chauffage par induction électromagnétique est un procédé efficace permettant de chauffer directement une zone d'épaisseur contrôlée sous la surface de pièces métalliques en vue…
(more)
▼ Le chauffage par induction électromagnétique est un procédé efficace permettant de chauffer directement une zone d'épaisseur contrôlée sous la surface de pièces métalliques en vue de les tremper. Cette thèse présente un modèle mathématique couplé électromagnétique/thermique et des approches numériques pour modéliser le procédé. Le modèle électromagnétique est basé sur une formulation en potentiel vecteur magnétique. Les courants de source sont imposés à l'aide d'une formulation en potentiel scalaire électrique permettant de modéliser des inducteurs de forme géométrique arbitraire. Le problème du transfert de chaleur est modélisé à l'aide de l'équation classique de diffusion de la chaleur. Le modèle électromagnétique est entièrement transitoire, afin de permettre l'introduction des effets non linéaires. La discrétisation spatiale est basée sur une approche éléments d'arêtes en utilisant un domaine global air/pièce/inducteur. Le système linéaire d'équations issu de la formulation implicite est creux et défini semi-positif ; il possède un noyau de taille importante. Il est démontré qu'un préconditionneur basé sur une méthode multigrille algébrique construit conjointement avec un solveur du type Krylov réduit substantiellement le temps de calcul du problème électromagnétique par rapport aux méthodes classiques de solution et peut être très efficace pour le calcul parallèle. Des exemples d'application pour le traitement thermique d'un pignon et pour un vilebrequin automobile sont présentés. Le traitement thermique des surfaces des pièces aux géométries complexes nécessite l'introduction d'un mouvement relatif de la pièce et de l'inducteur pour assurer un traitement homogène de la surface. Une nouvelle méthode est proposée, basée sur une représentation discrète d'une fonction level set du mouvement de l'inducteur qui peut être utilisée pour générer des maillages éléments finis conformes dans le cadre d'une configuration lagrangienne.
Electromagnetic induction heating is an efficient process allowing to directly heat up a prescribed area beneath the surface of metallic workpieces to enable quenching. This work presents a mathematical model for the coupled electromagnetic/heat transfer process as well as numerical solution methods. The electromagnetic model is based on a magnetic vector potential formulation. The source currents are prescribed using a voltage potential formulation enabling the modelling of arbitrary inductor geometries. The heat transfer problem is modelled using the classical heat diffusion equation. The electromagnetic model is fully transient, in order to allow the introduction of non-linear effects. The space discretisation is based on an edge finite element approach using a global domain including air, workpiece and inductor. The resulting linear system of equations of the implicit formulation is sparse and semi-definite, including a large kernel. It is demonstrated that a preconditioner based on the auxiliary space algebraic multigrid method in connection with a Krylov solver substantially reduces…
Advisors/Committee Members: Bay, François (thesis director).
Subjects/Keywords: Multigrille algébrique; Chauffage par induction.; Durcissement de surface; Équations de Maxwell; Éléments finis d’arêtes; Méthode level set; Algebraic multigrid; Induction heating.; Surface hardening; Maxwell’s equations; Edge finite elements; Level set method
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Klonk, S. (2013). Modélisation numérique du chauffage par induction de pièces à géométrie complexe : Numerical modelling of induction heating for complex geometrical parts. (Doctoral Dissertation). Paris, ENMP. Retrieved from http://www.theses.fr/2013ENMP0077
Chicago Manual of Style (16th Edition):
Klonk, Steffen. “Modélisation numérique du chauffage par induction de pièces à géométrie complexe : Numerical modelling of induction heating for complex geometrical parts.” 2013. Doctoral Dissertation, Paris, ENMP. Accessed March 05, 2021.
http://www.theses.fr/2013ENMP0077.
MLA Handbook (7th Edition):
Klonk, Steffen. “Modélisation numérique du chauffage par induction de pièces à géométrie complexe : Numerical modelling of induction heating for complex geometrical parts.” 2013. Web. 05 Mar 2021.
Vancouver:
Klonk S. Modélisation numérique du chauffage par induction de pièces à géométrie complexe : Numerical modelling of induction heating for complex geometrical parts. [Internet] [Doctoral dissertation]. Paris, ENMP; 2013. [cited 2021 Mar 05].
Available from: http://www.theses.fr/2013ENMP0077.
Council of Science Editors:
Klonk S. Modélisation numérique du chauffage par induction de pièces à géométrie complexe : Numerical modelling of induction heating for complex geometrical parts. [Doctoral Dissertation]. Paris, ENMP; 2013. Available from: http://www.theses.fr/2013ENMP0077
25.
Montagnier, Julien.
Etude de schémas numériques d'ordre élevé pour la simulation de dispersion de polluants dans des géométries complexes : Analysis of High-Order Finite Volume schemes for pollutant dispersion simulation in complex geometries.
Degree: Docteur es, Mécanique des fluides, 2010, Université Claude Bernard – Lyon I
URL: http://www.theses.fr/2010LYO10118
► La prévention des risques industriels nécessite de simuler la dispersion turbulente de polluants. Cependant, les outils majoritairement utilisés à ce jour ne permettent pas de…
(more)
▼ La prévention des risques industriels nécessite de simuler la dispersion turbulente de polluants. Cependant, les outils majoritairement utilisés à ce jour ne permettent pas de traiter les champs proches dans le cas de géométries complexes, et il est nécessaire d'utiliser les outils de CFD (“ Computational Fluid Dynamics ”) plus adaptés, mais plus coûteux. Afin de simuler les écoulements atmosphériques avec dispersion de polluants, les modèles CFD doivent modéliser correctement d'une part, les effets de flottabilité, et d'autre part les effets de la turbulence. Plusieurs approches existent, notamment dans la prise en compte des effets de flottabilité et la modélisation de la turbulence, et nécessitent des méthodes numériques adaptées aux spécificités mathématiques de chacune d'entre elles, ainsi que des schémas numériques précis pour ne pas polluer la modélisation. Une formulation d'ordre élevé en volumes finis, sur maillages non structurés, parallélisée, est proposée pour simuler les écoulements atmosphériques avec dispersion de polluants. L'utilisation de schémas d'ordre élevé doit permettre d'une part de réduire le nombre de cellules et diminuer les temps de simulation pour atteindre une précision donnée, et d'autre part de mieux contrôler la viscosité numérique des schémas en vue de simulations LES (Large Eddy Simulation), pour lesquelles la viscosité numérique des schémas peut masquer les effets de la modélisation. Deux schémas d'ordre élevé ont été étudiés et implémentés dans un solveur 3D Navier Stokes incompressible sur des maillages volumes finis non structurés. Nous avons développé un premier schéma d'ordre élevé, correspondant à un schéma Padé volumes finis, et nous avons étendu le schéma de reconstruction polynomiale de Carpentier (2000) aux écoulements incompressibles. Les propriétés numériques des différents schémas implémentés dans le même code de calcul sont étudiées sur différents cas tests bi-dimensionnels (calcul de flux convectifs et diffusifs sur une solution a-priori, convection d'une tâche gaussienne, décroissance d'un vortex de Taylor et cavité entraînée) et tri-dimensionnel (écoulement autour d'un obstacle cubique). Une attention particulière a été portée à l'étude de la précision et du traitement des conditions limites. L'implémentation proposée du schéma polynomial permet d'approcher, pour un maillage identique, les temps de simulation obtenus avec un schéma décentré classique d'ordre 2, mais avec une précision supérieure. Le schéma compact donne la meilleure précision. En utilisant une méthode de Jacobi sans calcul implicite de la matrice pour calculer le gradient, le temps de simulation devient intéressant uniquement lorsque la précision requise est importante. Une alternative est la résolution du système linéaire par une méthode multigrille algébrique. Cette méthode diminue considérablement le temps de calcul du gradient et le schéma Padé devient performant même pour des maillages grossiers. Enfin, pour réduire les temps de simulation, la parallélisation des schémas d'ordre élevé est…
Advisors/Committee Members: Buffat, Marc (thesis director).
Subjects/Keywords: Volumes finis; Ordre élevé; Incompressible Navier Stokes; Schéma Padé; Schéma d'ordre élevé polynomial; Solveur multigrille algébrique; GMRES; Finite volume; High order; Incompressible Navier Stokes; Padé scheme; High order polynomial; Algebraic multigrid solver; GMRES
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Montagnier, J. (2010). Etude de schémas numériques d'ordre élevé pour la simulation de dispersion de polluants dans des géométries complexes : Analysis of High-Order Finite Volume schemes for pollutant dispersion simulation in complex geometries. (Doctoral Dissertation). Université Claude Bernard – Lyon I. Retrieved from http://www.theses.fr/2010LYO10118
Chicago Manual of Style (16th Edition):
Montagnier, Julien. “Etude de schémas numériques d'ordre élevé pour la simulation de dispersion de polluants dans des géométries complexes : Analysis of High-Order Finite Volume schemes for pollutant dispersion simulation in complex geometries.” 2010. Doctoral Dissertation, Université Claude Bernard – Lyon I. Accessed March 05, 2021.
http://www.theses.fr/2010LYO10118.
MLA Handbook (7th Edition):
Montagnier, Julien. “Etude de schémas numériques d'ordre élevé pour la simulation de dispersion de polluants dans des géométries complexes : Analysis of High-Order Finite Volume schemes for pollutant dispersion simulation in complex geometries.” 2010. Web. 05 Mar 2021.
Vancouver:
Montagnier J. Etude de schémas numériques d'ordre élevé pour la simulation de dispersion de polluants dans des géométries complexes : Analysis of High-Order Finite Volume schemes for pollutant dispersion simulation in complex geometries. [Internet] [Doctoral dissertation]. Université Claude Bernard – Lyon I; 2010. [cited 2021 Mar 05].
Available from: http://www.theses.fr/2010LYO10118.
Council of Science Editors:
Montagnier J. Etude de schémas numériques d'ordre élevé pour la simulation de dispersion de polluants dans des géométries complexes : Analysis of High-Order Finite Volume schemes for pollutant dispersion simulation in complex geometries. [Doctoral Dissertation]. Université Claude Bernard – Lyon I; 2010. Available from: http://www.theses.fr/2010LYO10118
26.
Bienz, Amanda.
Reducing communication in sparse solvers.
Degree: PhD, Computer Science, 2018, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/101514
► Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication.…
(more)
▼ Sparse matrix operations dominate the cost of many scientific applications. In parallel, the performance and scalability of these operations is limited by irregular point-to-point communication. Multiple methods are investigated throughout this dissertation for reducing the cost associated with communication throughout sparse matrix operations. Algorithmic changes reduce communication requirements, but also affect accuracy of the operation, leading to reduced convergence of scientific codes. We investigate a method of systematically removing relatively small non-zeros throughout an
algebraic multigrid hierarchy, yielding significant reductions to the cost of sparse matrix-vector multiplication that outweigh affects of reduced accuracy of the multiplication. Therefore, the reduction in per-iteration communication costs outweigh the cost of extra solver iterations. As a result, sparsification yields improvement of both the performance and scalability of
algebraic multigrid.
Alterations to the parallel implementation of MPI communication also yield reduced costs with no effect on accuracy. We investigate methods of agglomerating messages on-node before injecting into the network, reducing the amount of costly inter-node communication. This node-aware communication yields improvements to both performance and scalability of matrix operations, particularly in strong scaling studies. Furthermore, we show an improvement in the cost of
algebraic multigrid as a result of reduced communication costs in sparse matrix operations.
Finally, performance models can be used to analyze the costs of matrix operations, indicating the source of dominant communication costs, such as initializing messages or transporting bytes of data. We investigate methods of improving traditional performance models of irregular point-to-point communication through the addition of node-awareness, queue search costs, and network contention penalties.
Advisors/Committee Members: Olson, Luke N (advisor), Olson, Luke N (Committee Chair), Gropp, William D (committee member), Solomonik, Edgar (committee member), Grigori, Laura (committee member).
Subjects/Keywords: Sparse solvers; Linear solvers; Parallel programming; Parallel communication; Algebraic multigrid; Performance modeling
…communicated through
the network.
Algebraic multigrid setup and solve phases: Node-aware… …communication is applied throughout both the setup and solve phases of algebraic multigrid in Chapter… …760,648,352 non-zeros
2.2 ALGEBRAIC MULTIGRID
In this section we detail the AMG setup and solve… …sparse matrix-matrix
(SpGEMM) multiply on the levels of an algebraic multigrid (… …only
necessary values to the processes that need them.
Algebraic multigrid (AMG) is…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Bienz, A. (2018). Reducing communication in sparse solvers. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/101514
Chicago Manual of Style (16th Edition):
Bienz, Amanda. “Reducing communication in sparse solvers.” 2018. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 05, 2021.
http://hdl.handle.net/2142/101514.
MLA Handbook (7th Edition):
Bienz, Amanda. “Reducing communication in sparse solvers.” 2018. Web. 05 Mar 2021.
Vancouver:
Bienz A. Reducing communication in sparse solvers. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2018. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/2142/101514.
Council of Science Editors:
Bienz A. Reducing communication in sparse solvers. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2018. Available from: http://hdl.handle.net/2142/101514
27.
-2628-3585.
Scalable, adaptive methods for forward and inverse problems in continental-scale ice sheet modeling.
Degree: PhD, Computational and applied mathematics, 2015, University of Texas – Austin
URL: http://hdl.handle.net/2152/31372
► Projecting the ice sheets' contribution to sea-level rise is difficult because of the complexity of accurately modeling ice sheet dynamics for the full polar ice…
(more)
▼ Projecting the ice sheets' contribution to sea-level rise is difficult because of the complexity of accurately modeling ice sheet dynamics for the full polar ice sheets, because of the uncertainty in key, unobservable parameters governing those dynamics, and because quantifying the uncertainty in projections is necessary when determining the confidence to place in them. This work presents the formulation and solution of the Bayesian inverse problem of inferring, from observations, a probability distribution for the basal sliding parameter field beneath the Antarctic ice sheet. The basal sliding parameter is used within a high-fidelity nonlinear Stokes model of ice sheet dynamics. This model maps the parameters "forward" onto a velocity field that is compared against observations. Due to the continental-scale of the model, both the parameter field and the state variables of the forward problem have a large number of degrees of freedom: we consider discretizations in which the parameter has more than 1 million degrees of freedom. The Bayesian inverse problem is thus to characterize an implicitly defined distribution in a high-dimensional space. This is a computationally demanding problem that requires scalable and efficient numerical methods be used throughout: in discretizing the forward model; in solving the resulting nonlinear equations; in solving the Bayesian inverse problem; and in propagating the uncertainty encoded in the posterior distribution of the inverse problem forward onto important quantities of interest. To address discretization, a hybrid parallel adaptive mesh refinement format is designed and implemented for ice sheets that is suited to the large width-to-height aspect ratios of the polar ice sheets. An efficient solver for the nonlinear Stokes equations is designed for high-order, stable, mixed finite-element discretizations on these adaptively refined meshes. A Gaussian approximation of the posterior distribution of parameters is defined, whose mean and covariance can be efficiently and scalably computed using adjoint-based methods from PDE-constrained optimization. Using a low-rank approximation of the covariance of this distribution, the covariance of the parameter is pushed forward onto quantities of interest.
Advisors/Committee Members: Ghattas, Omar N. (advisor), Stadler, Georg, Ph. D. (advisor), Arbogast, Todd (committee member), Biros, George (committee member), Catania, Ginny (committee member), Oden, John Tinsley (committee member).
Subjects/Keywords: Ice sheets; Parameter estimation; PDE-constrained optimization; Bayesian inversion; Adaptive mesh refinement; Quadtrees/octrees; Algebraic multigrid; Randomized methods
…Burstedde et al., 2010] (see figure 2.2) to geometric multigrid hierarchy…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
-2628-3585. (2015). Scalable, adaptive methods for forward and inverse problems in continental-scale ice sheet modeling. (Doctoral Dissertation). University of Texas – Austin. Retrieved from http://hdl.handle.net/2152/31372
Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete
Chicago Manual of Style (16th Edition):
-2628-3585. “Scalable, adaptive methods for forward and inverse problems in continental-scale ice sheet modeling.” 2015. Doctoral Dissertation, University of Texas – Austin. Accessed March 05, 2021.
http://hdl.handle.net/2152/31372.
Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete
MLA Handbook (7th Edition):
-2628-3585. “Scalable, adaptive methods for forward and inverse problems in continental-scale ice sheet modeling.” 2015. Web. 05 Mar 2021.
Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete
Vancouver:
-2628-3585. Scalable, adaptive methods for forward and inverse problems in continental-scale ice sheet modeling. [Internet] [Doctoral dissertation]. University of Texas – Austin; 2015. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/2152/31372.
Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete
Council of Science Editors:
-2628-3585. Scalable, adaptive methods for forward and inverse problems in continental-scale ice sheet modeling. [Doctoral Dissertation]. University of Texas – Austin; 2015. Available from: http://hdl.handle.net/2152/31372
Note: this citation may be lacking information needed for this citation format:
Author name may be incomplete
28.
Λαμπρόπουλος, Νικόλαος.
Τεχνικές πολυπλέγματος σε μη-δομημένα πλέγματα για την αριθμητική επίλυση πεδίων ροής στις στροβιλομηχανές, σε πολυεπεξεργαστικό περιβάλλον.
Degree: 2005, National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ)
URL: http://hdl.handle.net/10442/hedi/17452
Subjects/Keywords: Υπολογιστική ρευστοδυναμική; Αλγεβρική τεχνική πολυπλέγματος; Μη δομημένα πλέγματα; Πλήρης τεχνική πολυπλέγματος; Σχήμα πλήρους προσέγγισης; Παράλληλη επεξεργασία; Τυρβώδεις ροές; Computational fluid dynamics; Algebraic multigrid techniques; Unstructured grids; Full multigrid techniques; Full approximation scheme; Parallel computing; Thermal turbomachines; Turbulent flows
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Λαμπρόπουλος, . . (2005). Τεχνικές πολυπλέγματος σε μη-δομημένα πλέγματα για την αριθμητική επίλυση πεδίων ροής στις στροβιλομηχανές, σε πολυεπεξεργαστικό περιβάλλον. (Thesis). National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Retrieved from http://hdl.handle.net/10442/hedi/17452
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Λαμπρόπουλος, Νικόλαος. “Τεχνικές πολυπλέγματος σε μη-δομημένα πλέγματα για την αριθμητική επίλυση πεδίων ροής στις στροβιλομηχανές, σε πολυεπεξεργαστικό περιβάλλον.” 2005. Thesis, National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Accessed March 05, 2021.
http://hdl.handle.net/10442/hedi/17452.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Λαμπρόπουλος, Νικόλαος. “Τεχνικές πολυπλέγματος σε μη-δομημένα πλέγματα για την αριθμητική επίλυση πεδίων ροής στις στροβιλομηχανές, σε πολυεπεξεργαστικό περιβάλλον.” 2005. Web. 05 Mar 2021.
Vancouver:
Λαμπρόπουλος . Τεχνικές πολυπλέγματος σε μη-δομημένα πλέγματα για την αριθμητική επίλυση πεδίων ροής στις στροβιλομηχανές, σε πολυεπεξεργαστικό περιβάλλον. [Internet] [Thesis]. National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ); 2005. [cited 2021 Mar 05].
Available from: http://hdl.handle.net/10442/hedi/17452.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Λαμπρόπουλος . Τεχνικές πολυπλέγματος σε μη-δομημένα πλέγματα για την αριθμητική επίλυση πεδίων ροής στις στροβιλομηχανές, σε πολυεπεξεργαστικό περιβάλλον. [Thesis]. National Technical University of Athens (NTUA); Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ); 2005. Available from: http://hdl.handle.net/10442/hedi/17452
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
. 
Open Access Theses and Dissertations
