When solving stochastic partial differential equations with random coefficients, the stochastic Galerkin method results in a large single system via a traditional finite element discretization in the spatial domain and generalized polynomial chaos in the stochastic space. The sparse pattern on the stochastic Galerkin matrix can be described by a simplex lattice structure. With the help of this simplex structure, it is shown that the spectrum of the mean-based preconditioning system is symmetric with respect to one and a tighter eigen-bound for the mean-based preconditioned system is developed. Furthermore, a new variance-involved block diagonal preconditioner and a new block triangular preconditioner based on the simplex lattice structure are proposed and their corresponding spectral analyses are studied. Numerical experiments show that the new preconditioners are more robust and efficient compared to the mean-based preconditioner, especially when the variance and the total polynomial degree in the complete stochastic space are large. The block triangular preconditioner is extended to a stochastic diffusion problem with mixed formulation together with a new mean-based block triangular preconditioner. Both preconditioners outperform the traditional mean-based diagonal preconditioner on a benchmark problem.

Finite element exterior calculus (FEEC) is a framework to design and understand finite element discretizations for a wide variety of systems of partial differential equations. The applications are already made to the Hodge Laplacian, Maxwell’s equations, the equations of elasticity, elliptic eigenvalue problems and etc.. In this thesis, we propose fast solvers for several numerical schemes based on the discretization of this approach and present theoretical analysis. Specifically, in the first part, we propose efficient block diagonal and block triangular preconditioners for solving the discretized linear system of the vector Laplacian by mixed finite element methods. A variable V-cycle multigrid method with the standard point-wise Gauss-Seidel smoother is proved to be a good preconditioner for the Schur complement. The major benefit of our approach is that the point-wise Gauss-Seidel smoother is more algebraic and can be easily implemented as a ‘black-box’ smoother. The multigrid solver for the Schur complement will be further used to build preconditioners for the original saddle point systems. In the second part, we propose a discretization method for the Darcy-Stokes equations under the framework of FEEC. The discretization is shown to be uniform with respect to the perturbation parameter. A preconditioner for the discrete system is also proposed and shown to be efficient. In the last part, we focus on the stochastic Stokes equations. The stochastic saddle-point linear systems are obtained by using finite element discretization under the framework of FEEC in physical space and generalized polynomial chaos expansion in random space. We prove the existence and uniqueness of the solutions to the continuous problem and its corresponding stochastic Galerkin discretization. Optimal error estimates are also derived. We construct block-diagonal/triangular preconditioners for use with the generalized minimum residual method and the bi-conjugate gradient stabilized method. An optimal multigrid solver is applied to efficiently solve the diagonal blocks that correspond to deterministic discrete Stokes systems. To demonstrate the efficiency and robustness of the discretization methods and proposed preconditioners, various numerical examples also are provided.

In this thesis, we propose different numerical methods for solving elliptic interface problems in three dimensions and moving boundary problems in two dimensions. In the first part, a simple and efficient interface-fitted mesh algorithm which can produce a semi-unstructured interface-fitted mesh in two and three dimensions quickly is developed in this thesis. Elements in such interface- fitted meshes are not restricted to simplices but can be polygons or polyhedra. Especially in 3D, the polyhedra instead of tetrahedra can avoid slivers, which are the major difficulty in finite element methods. Virtual element methods are applied to solve elliptic interface problems with solutions and flux jump conditions. Algebraic multigrid solvers are used to solve the resulting linear al- gebraic system. In the second part, we impose the interface-fitted meshes to moving boundary problems and present the applications in biology simulation. Static interface problems with peri- odic conditions are considered at first, then the higher order accuracy algorithm is also developed. Finally moving interface problems are discussed. We couple the interface Poisson equation and the transport equation for the level set function together to simulate the tissue and tumor growth phenomenon. Numerical results are presented to illustrate the effectiveness of our methods.

We present stabilized virtual element methods for convection-diffusion problems in the convection-dominated regime. In the context of finite element methods, the edge-averaged finite element schemes were successfully applied to convection-dominated problems. We aim to generalize the edge-averaged stabilization to the virtual element framework. Hence, we develop the edge-averaged virtual element methods that produce numerical solutions on polygonal meshes without spurious oscillations caused by small diffusion coefficients. Well-posedness of the discrete problem and convergence analysis are provided. We also show numerical experiments which support theoretical results, and display numerical solutions with sharp boundary layers in the convection-dominated regime.

Saddle point problems are crucial due to their pervasive applications across various scientific and engineering fields. In this work, we focus on iterative methods for solving smooth convex-concave saddle point problems with bilinear coupling. Initially, we introduce an accelerated over-relaxation heavy-ball method specifically designed for strongly-convex-strongly-concave saddle point problems. This marks the first instance where the heavy-ball method extended beyond convex optimization, retaining a provable global convergence and demonstrating accelerated convergence rate. Subsequently, for saddle point problems from constrained optimization, we develop a novel transformed primal-dual flow. The discretization of this flow leads to a series of transformed primal-dual methods. By revealing approximated Schur complement in the transformed primal-dual methods, the algorithms achieve global and linear convergence for convex-concave saddle point problems. With acceleration technique, the accelerated transform primal-dual method achieve the optimal computation complexity for solving affine equality constrained problems. When addressing the saddle point problems arising in numerical partial differential equations, we present the transformed primal-dual method with variable preconditioners. Numerical experiments involving machine learning tasks and partial differential equations highlight the superior performance of our algorithm compared to existing methods and support our theoretical results.