Chen Greif

This thesis deals with the mathematical analysis and numerical solution of double saddle-point systems.We derive bounds on the eigenvalues of a generic form of double saddle-point matrices with a positive definite leading block. The bounds are expressed in terms of extremal eigenvalues and singular values of the associated block matrices. Inertia and algebraic multiplicity of eigenvalues are considered as well. The analysis includes bounds for preconditioned matrices based on block diagonal preconditioners using Schur complements, and it is shown that in this case the eigenvalues are clustered within a few intervals bounded away from zero. Analysis for approximations of Schur complements is included. Some numerical observations validate our analytical findings.We also derive bounds on the eigenvalues of (classical) saddle-point matrices with singular leading blocks. The technique of proof is based on augmentation. Our bounds depend on the principal angles between the ranges or kernels of the matrix blocks. We use these analyses to derive a preconditioner for saddle-point systems with singular leading blocks. Our preconditioning approach is based on augmenting the leading block and using Schur complements of the augmented system. We show that the resulting preconditioned operator has four distinct eigenvalues, and numerical experiments validate the effectiveness of our approach.We then extend the preconditioner for saddle-point systems with a singular leading block to deal with double saddle-point systems with a singular leading block. The preconditioner is based on augmenting the leading block by a null matrix of one of the off-diagonal blocks, and using the Schur complements of the augmented system.

View record

This thesis investigates several aspects of the optimal mapping problem, finding a bijective function between two shapes which minimizes some metric, and its many applications in computer graphics such as finding planar embeddings of curved surface meshes, image warping, mesh deformation, elastoplastic simulation, and more. We highlight in particular problems where differences in topology between the shapes—which necessitate discontinuities in the mapping—play a crucial role, e.g. due to animation decisions or physical fracture. Our first project presents an approach to extend discrete variational shape interpolation to create keyframe animation involving extreme deformation, topology change and dynamics. To construct correspondence between keyframe shapes as well as satisfying feature matching constraints, we introduce a consistent multimesh structure that is able to resolve topological in-equivalence between shapes and a Comesh Optimization algorithm that optimizes our multimesh for both intra and inter-mesh quality. To further speed up the total solving time, we then develop three new improvements to the state of the art nonlinear optimization techniques that are frequently used in this field, including a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms; an energy proxy model that adaptively blends the Sobolev gradient and L-BFGS descent to gain the advantages of both; and a characteristic gradient norm providing a robust and largely mesh- and energy independent convergence criterion. Finally, we demonstrate another related interesting graphics application, brittle fracture simulation. In particular, we investigate whether we can sidestep the volumetric optimal mapping problem for solving elastic deformation and instead use a boundary element discretization which only requires a surface mesh. We will show how the computational cost of such problems can be alleviated using a boundary integral formulation and kernel-independent Fast Multipole Method. By combining with an explicit surface tracking framework, we further avoid the expensive volumetric mesh construction and maintenance during fracture propagation and shape topology change.

View record

The main goal of this thesis is to design efficient numerical solutions to incompressible magnetohydrodynamics (MHD) problems, with focus on the solution of the large and sparse linear systems that arise. The MHD model couples the Navier-Stokes equations that govern fluid dynamics and Maxwell's equations which govern the electromagnetic effects.We consider a mixed finite element discretization of an MHD model problem. Upon discretization and linearization, a large block 4-by-4 nonsymmetric linear system needs to be (repeatedly) solved. One of the principal challenges is the presence of a skew-symmetric term that couples the fluid velocity with the magnetic field.We propose two distinct preconditioning techniques. The first approach relies on utilizing and combining effective solvers for the mixed Maxwell and the Navier-Stokes sub-problems. The second approach is based on algebraic approximations of the inverse of the matrix of the linear system. Both approaches exploit the block structure of the discretized MHD problem.We perform a spectral analysis for ideal versions of the proposed preconditioners, and develop and test practical versions.Large-scale numerical results for linear systems of dimensions up to 10⁷ in two and three dimensions validate the effectiveness of our techniques.We also explore the use of the Conjugate Gradient (CG) method for saddle-point problems with an algebraic structure similar to the time-harmonic Maxwell problem. Specifically, we show that for a nonsingular saddle-point matrix with a maximally rank-deficient leading block, there are two sufficient conditions that allow for CG to be used.An important part of the contributions of this thesis is the development of numerical software that utilizes state-of-the-art software packages. This software is highly modular, robust, and flexible.

View record

Turbulent gaseous phenomena, often visually characterized by their swirling nature,are mostly dominated by the evolution of vorticity. Small scale vortex structuresare essential to the look of smoke, fire, and related effects, whether producedby vortex interactions, jumps in density across interfaces (baroclinity), orviscous boundary layers. Classic Eulerian fluid solvers do not cost-effectively capturethese small-scale features in large domains. Lagrangian vortex methods showgreat promise from turbulence modelling, but face significant challenges in handlingboundary conditions, making them less attractive for computer graphics applications.This thesis proposes several novel solutions for the efficient simulationof small scale vortex features both in Eulerian and Lagrangian frameworks, extendingrobust Eulerian simulations with new algorithms inspired by Lagrangianvortex methods.

View record

The goal of this thesis is to develop efficient numerical solvers for the time-harmonicMaxwell equations and for incompressible magnetohydrodynamics problems.The thesis consists of three components. In the first part, we present a fullyscalable parallel iterative solver for the time-harmonic Maxwell equations in mixedform with small wave numbers. We use the lowest order Nedelec elements of thefirst kind for the approximation of the vector field and standard nodal elements forthe Lagrange multiplier associated with the divergence constraint. The correspondinglinear system has a saddle point form, with inner iterations solved by preconditioned conjugate gradients. We demonstrate the performance ofour parallel solver on problems with constant and variable coefficients with up toapproximately 40 million degrees of freedom. Our numerical results indicate verygood scalability with the mesh size, on uniform, unstructured and locally refinedmeshes.In the second part, we introduce and analyze a mixed finite element method forthe numerical discretization of a stationary incompressible magnetohydrodynamicsproblem, in two and three dimensions. The velocity field is discretized usingdivergence-conforming Brezzi-Douglas-Marini (BDM) elements and the magneticfield is approximated by curl-conforming Nedelec elements. Key features of themethod are that it produces exactly divergence-free velocity approximations, andthat it correctly captures the strongest magnetic singularities in non-convex polyhedraldomains. We prove that the energy norm of the error is convergent in themesh size in general Lipschitz polyhedra under minimal regularity assumptions,and derive nearly optimal a-priori error estimates for the two-dimensional case. Wepresent a comprehensive set of numerical experiments, which indicate optimal convergence of the proposed method for two-dimensional as well as three-dimensionalproblems.Finally, in the third part we investigate preconditioned Krylov iterations forthe discretized stationary incompressible magnetohydrodynamics problems. Wepropose a preconditioner based on efficient preconditioners for the Maxwell andNavier-Stokes sub-systems. We show that many of the eigenvalues of the preconditionedsystem are tightly clustered, and hence, rapid convergence is accomplished.Our numerical results show that this approach performs quite well.

View record