#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