#title Multigrid methods for convection-dominated elliptic equations
* slides
** introduction, motivation
multigrid for problems with convection
convection diffusion equations
convection dominated problems
example
\[\epsilon \nabla u + b u + f = 0\]
elliptic as long as \(\epsilon > 0\)
convection dominated \(\epsilon\) very small
singularly perturbed problem
standard mg breaks down
example from paper
Navier-Stokes
\[u_t + \epsilon \Delta u + (u \cdot \nabla) u + \nabla p = f\]
\[\nabla \cdot u = 0\]
Stokes
\[\epsilon \Delta u + (b \cdot \nabla) u + \theta u + \nabla p = f\]
\[\nabla \cdot u = 0\]
linearised model problem
** extreme cases
elliptic, standard multigrid works very well
convection, no cycles, Gauss-Seidel in direction of flow is direct solver
with appropriate ordering triangular system
what if cycles
approach of paper: try to find good ordering
different approaches
** ordering algorithms
in paper
triangular or downwind (acyclic, block version -> strongly connected components)
reverse Cuthill-McKee RCM (undirected graph, sparsity)
heuristic feedback vertex set HFVS (directed graph, "large" elements)
concentric cycles CC (coordinates (planar), one-flow-direction condition)
(planar) feedback vertex set PFVS (coordinates (planar), one-flow-direction condition)
** graph theory
picture
graph, successor, predecessor, degree, subgraph, path, cycle, weakly
connected, strongly connected, components, quotient graph
** matrix graph
matrix graph, reduced matrix graph of dominant entries
ordering
** triangular ordering
acyclic graph : no cycles
topological sort, assign number such that each smaller than successors
algorithm in paper
corresponding matrix -> triangular
for graph with strongly connected components -> apply to quotient
matrix (vertex for each component)
block triangular matrix
following algorithms for the strongly connected components
** concentric cycles
one-flow-direction condition
picture with and without
leftmost (rightmost) outward edge
left -> minimal cycle
right -> maximal cycle
algorithm
vertex, cycle, remove, update attributes, remove vertices not on cycle, repeat
first nodes in triangular order, cycles, last nodes in triangular orders
block matrix with easy to invert blocks on the diagonal
** feedback vertex set ordering
F is FVS if every cycle at least one vertex of F
minimal FVS
equivalently : set that if removed gives acyclic graph
first vertices in FVS, rest by triangular ordering
NP-complete
quasi-optimal FVS, within factor of minimal (here 2)
algorithm (planar graph)
define interior and exterior of cycles
assign value to each vertex based on number of interiors/exteriors it
belongs to
quasi-optimal and can be implemented efficiently (linear)
to complicated to go into details (paper doesn't really either)
** weighted graphs
** parallel flow ordering
** heuristic feedback vertex set algorithm
not necessarily quasi-optimal, not necessarily linear time
no geometric information (coordinates, one-flow-direction)
many cases sufficiently small set in acceptable time
transformation that remove one vertex from graph
pictures
apply repeatedly and recursively
if all vertices can be removed this way -> two-way reducible graph
otherwise remove node and continue, high or max degree (local search,
update info about this for efficiency)
** reverse Cuthill-McKee
only based on connectivity (combinatorial), not geometry, not weights
algorithm
- find good starting vertex
- add all unconsidered vertices following current in order of their degree, next
- use the reverse of the resulting numbering
good starting vertex
- distance between vertices : length of shortest path between vertices
- eccentricity of vertex : maximum distance to any other vertex
- diameter of graph : maximum eccentricity
- radius of graph : minimum eccentricity
- centre : vertex with minimum eccentricity (ecc(v) = rad(G))
- peripheral vertex : vertex with maximum eccentricity (ecc(v) = diam(G))
approximately peripheral pair
- start with random vertex
- do BFS (flood) for furthest vertex (ecc)
- repeat starting from the found vertex
- repeat as long as the eccentricity increases
** 3D
many algorithms don't apply or may be more expensive
reduce to 2D by determining interior surfaces
picture cylinder
definition of surface
- degree of edge <= 2
- connected (path between any two faces)
- faces sharing vertex have connecting path "around" vertex
flow surface
consider flow vector
algorithm to determine surface "parallel" to flow
find surface, remove surface and all faces that share vertex with it, repeat
** iterative methods
Stokes problem, block factorization, Schur complement
Gauss-Seidel for convection-diffusion blocks for velocity components
ILU of whole matrix used to approximate Schur complement
this as preconditioner or smoother
standard multigrid
** numerical results
experiment 1 : curve
experiment 2 : circle
in other papers : 4 circles
** conclusions
for acyclic, towords direct for convection-dominated
no longer for cycles, but still considerable improvement
from the numerical results I conclude that
RCM with symmetric GS works quite well
RCM is a well established technique for solving sparse systems
many implementations available
worth giving this a try before coding up something else
other matrix reordering techniques exist
AMD is used in UMFPACK (Matlab) for example
RCM and AMD are not easy to parallelise
another option (hierarchical) self-avoiding walk (combinatorial)
** for us
main interest extend domain decomposition to nonsymmetric problems (convection)
not clear how well these techniques parallelise
* paper
** introduction
incompressible Navier-Stokes
2D, 3D
singularly perturbed
linearized variant, Stokes problem
discretization
sparsity, convection direction
** ordering techniques
*** graph theory
graph, successor, predecessor, degree, subgraph, path, cycle,
connectivity, quotient graph
*** matrix graph
matrix graph, reduced matrix graph of dominant entries
*** triangular ordering
downwind ordering
*** block triangular ordering
strongly connected components
*** one-flow-direction condition
*** concentric cycles
*** feedback vertex set ordering
*** quasi-optimal feedback vertex set algorithm
*** weighted graphs
*** parallel flow
** heuristic feedback vertex set algorithm
** 3D
*** interior surfaces
*** surfaces, surface graphs
*** flow surface
*** surface algorithm
*** one-flow-direction condition
** iterative methods
** numerical results
*** discretization
*** multigrid
*** ordering
*** experiment 1 : curve
*** experiment 2 : circle
** conclusion