BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jinchao Xu

Jinchao Xu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical AnalysisMachine LearningComputer Visioneess.IVInformation Theorymath.APmath.CAmath.ITmath.OCmath.STphysics.comp-phphysics.flu-dynStatistics Theory

Catalog footprint

What is connected

42works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

42 published item(s)

preprint2026arXiv

Solving High-Dimensional PDEs Using Linearized Neural Networks

Linearized shallow neural networks that are constructed by fixing the hidden-layer parameters have recently shown strong performance in solving partial differential equations (PDEs). Such models, widely used in the random feature method (RFM) and extreme learning machines (ELM), transform network training into a linear least-squares problem. In this paper, we conduct a numerical study of the variational (Galerkin) and collocation formulations for these linearized networks. Our numerical results reveal that, in the variational formulation, the associated linear systems are severely ill-conditioned, forming the primary computational bottleneck in scaling the neural network size, even when direct solvers are employed. In contrast, collocation methods combined with robust least-squares solvers exhibit better numerical stability and achieve higher accuracy as we increase neuron numbers. This behavior is consistently observed for both ReLU$^k$ and $\tanh$ activations, with $\tanh$ networks exhibiting even worse conditioning. Furthermore, we demonstrate that random sampling of the hidden layer parameters, commonly used in RFM and ELM, is not necessary for achieving high accuracy. For ReLU$^k$ activations, this follows from existing theory and is verified numerically in this paper, while for $\tanh$ activations, we introduce two deterministic schemes that achieve comparable accuracy.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Priori Analysis of Stable Neural Network Solutions to Numerical PDEs

Methods for solving PDEs using neural networks have recently become a very important topic. We provide an a priori error analysis for such methods which is based on the $\mathcal{K}_1(\mathbb{D})$-norm of the solution. We show that the resulting constrained optimization problem can be efficiently solved using a greedy algorithm, which replaces stochastic gradient descent. Following this, we show that the error arising from discretizing the energy integrals is bounded both in the deterministic case, i.e. when using numerical quadrature, and also in the stochastic case, i.e. when sampling points to approximate the integrals. In the later case, we use a Rademacher complexity analysis, and in the former we use standard numerical quadrature bounds. This extends existing results to methods which use a general dictionary of functions to learn solutions to PDEs and importantly gives a consistent analysis which incorporates the optimization, approximation, and generalization aspects of the problem. In addition, the Rademacher complexity analysis is simplified and generalized, which enables application to a wide range of problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A sharp Korn's inequality for piecewise $H^1$ space and its application

In this paper, we revisit Korn's inequality for the piecewise $H^1$ space based on general polygonal or polyhedral decompositions of the domain. Our Korn's inequality is expressed with minimal jump terms. These minimal jump terms are identified by characterizing the restriction of rigid body mode to edge/face of the partitions. Such minimal jump conditions are shown to be sharp for achieving the Korn's inequality as well. The sharpness of our result and explicitly given minimal conditions can be used to test whether any given finite element spaces satisfy Korn's inequality, immediately as well as to build or modify nonconforming finite elements for Korn's inequality to hold.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Approximation Properties of Deep ReLU CNNs

This paper focuses on establishing $L^2$ approximation properties for deep ReLU convolutional neural networks (CNNs) in two-dimensional space. The analysis is based on a decomposition theorem for convolutional kernels with a large spatial size and multi-channels. Given the decomposition result, the property of the ReLU activation function, and a specific structure for channels, a universal approximation theorem of deep ReLU CNNs with classic structure is obtained by showing its connection with one-hidden-layer ReLU neural networks (NNs). Furthermore, approximation properties are obtained for one version of neural networks with ResNet, pre-act ResNet, and MgNet architecture based on connections between these networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Characterization of the Variation Spaces Corresponding to Shallow Neural Networks

We study the variation space corresponding to a dictionary of functions in $L^2(Ω)$ for a bounded domain $Ω\subset \mathbb{R}^d$. Specifically, we compare the variation space, which is defined in terms of a convex hull with related notions based on integral representations. This allows us to show that three important notions relating to the approximation theory of shallow neural networks, the Barron space, the spectral Barron space, and the Radon BV space, are actually variation spaces with respect to certain natural dictionaries.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Extended Regularized Dual Averaging Methods for Stochastic Optimization

We introduce a new algorithm, extended regularized dual averaging (XRDA), for solving regularized stochastic optimization problems, which generalizes the regularized dual averaging (RDA) method. The main novelty of the method is that it allows a flexible control of the backward step size. For instance, the backward step size used in RDA grows without bound, while for XRDA the backward step size can be kept bounded. We demonstrate experimentally that additional control over the backward step size can significantly improve the convergence rate of the algorithm while preserving desired properties of the iterates, such as sparsity. Theoretically, we show that the XRDA method achieves the same convergence rate as RDA for general convex objectives.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Convergence Rates for the Orthogonal Greedy Algorithm

We analyze the orthogonal greedy algorithm when applied to dictionaries $\mathbb{D}$ whose convex hull has small entropy. We show that if the metric entropy of the convex hull of $\mathbb{D}$ decays at a rate of $O(n^{-\frac{1}{2}-α})$ for $α> 0$, then the orthogonal greedy algorithm converges at the same rate on the variation space of $\mathbb{D}$. This improves upon the well-known $O(n^{-\frac{1}{2}})$ convergence rate of the orthogonal greedy algorithm in many cases, most notably for dictionaries corresponding to shallow neural networks. These results hold under no additional assumptions on the dictionary beyond the decay rate of the entropy of its convex hull. In addition, they are robust to noise in the target function and can be extended to convergence rates on the interpolation spaces of the variation norm. We show empirically that the predicted rates are obtained for the dictionary corresponding to shallow neural networks with Heaviside activation function in two dimensions. Finally, we show that these improved rates are sharp and prove a negative result showing that the iterates generated by the orthogonal greedy algorithm cannot in general be bounded in the variation norm of $\mathbb{D}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

ReLU Deep Neural Networks from the Hierarchical Basis Perspective

We study ReLU deep neural networks (DNNs) by investigating their connections with the hierarchical basis method in finite element methods. First, we show that the approximation schemes of ReLU DNNs for $x^2$ and $xy$ are composition versions of the hierarchical basis approximation for these two functions. Based on this fact, we obtain a geometric interpretation and systematic proof for the approximation result of ReLU DNNs for polynomials, which plays an important role in a series of recent exponential approximation results of ReLU DNNs. Through our investigation of connections between ReLU DNNs and the hierarchical basis approximation for $x^2$ and $xy$, we show that ReLU DNNs with this special structure can be applied only to approximate quadratic functions. Furthermore, we obtain a concise representation to explicitly reproduce any linear finite element function on a two-dimensional uniform mesh by using ReLU DNNs with only two hidden layers.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Approximation Rates for Neural Networks with General Activation Functions

We prove some new results concerning the approximation rate of neural networks with general activation functions. Our first result concerns the rate of approximation of a two layer neural network with a polynomially-decaying non-sigmoidal activation function. We extend the dimension independent approximation rates previously obtained to this new class of activation functions. Our second result gives a weaker, but still dimension independent, approximation rate for a larger class of activation functions, removing the polynomial decay assumption. This result applies to any bounded, integrable activation function. Finally, we show that a stratified sampling approach can be used to improve the approximation rate for polynomially decaying activation functions under mild additional assumptions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Abstract Stabilization Method with Applications to Nonlinear Incompressible Elasticity

In this paper, we propose and analyze an abstract stabilized mixed finite element framework that can be applied to nonlinear incompressible elasticity problems. In the abstract stabilized framework, we prove that any mixed finite element method that satisfies the discrete inf-sup condition can be modified so that it is stable and optimal convergent as long as the mixed continuous problem is stable. Furthermore, we apply the abstract stabilized framework to nonlinear incompressible elasticity problems and present numerical experiments to verify the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Constrained Linear Data-feature Mapping for Image Classification

In this paper, we propose a constrained linear data-feature mapping model as an interpretable mathematical model for image classification using convolutional neural network (CNN) such as the ResNet. From this viewpoint, we establish the detailed connections in a technical level between the traditional iterative schemes for constrained linear system and the architecture for the basic blocks of ResNet. Under these connections, we propose some natural modifications of ResNet type models which will have less parameters but still maintain almost the same accuracy as these corresponding original models. Some numerical experiments are shown to demonstrate the validity of this constrained learning data-feature mapping assumption.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust block preconditioners for poroelasticity

In this paper we study the linear systems arising from discretized poroelasticity problems. We formulate one block preconditioner for the two-filed Biot model and several preconditioners for the classical three-filed Biot model under the unified relationship framework between well-posedness and preconditioners. By the unified theory, we show all the considered preconditioners are uniformly optimal with respect to material and discretization parameters. Numerical tests demonstrate the robustness of these preconditioners.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

ReLU Deep Neural Networks and Linear Finite Elements

In this paper, we investigate the relationship between deep neural networks (DNN) with rectified linear unit (ReLU) function as the activation function and continuous piecewise linear (CPWL) functions, especially CPWL functions from the simplicial linear finite element method (FEM). We first consider the special case of FEM. By exploring the DNN representation of its nodal basis functions, we present a ReLU DNN representation of CPWL in FEM. We theoretically establish that at least $2$ hidden layers are needed in a ReLU DNN to represent any linear finite element functions in $Ω\subseteq \mathbb{R}^d$ when $d\ge2$. Consequently, for $d=2,3$ which are often encountered in scientific and engineering computing, the minimal number of two hidden layers are necessary and sufficient for any CPWL function to be represented by a ReLU DNN. Then we include a detailed account on how a general CPWL in $\mathbb R^d$ can be represented by a ReLU DNN with at most $\lceil\log_2(d+1)\rceil$ hidden layers and we also give an estimation of the number of neurons in DNN that are needed in such a representation. Furthermore, using the relationship between DNN and FEM, we theoretically argue that a special class of DNN models with low bit-width are still expected to have an adequate representation power in applications. Finally, as a proof of concept, we present some numerical results for using ReLU DNNs to solve a two point boundary problem to demonstrate the potential of applying DNN for numerical solution of partial differential equations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Algebraic Multigrid Methods

This paper is to give an overview of AMG methods for solving large scale systems of equations such as those from the discretization of partial differential equations. AMG is often understood as the acronym of "Algebraic Multi-Grid", but it can also be understood as "Abstract Muti-Grid". Indeed, as it demonstrates in this paper, how and why an algebraic multigrid method can be better understood in a more abstract level. In the literature, there are a variety of different algebraic multigrid methods that have been developed from different perspectives. In this paper, we try to 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, we prove that the optimal coarse space of dimension $n_c$ is the span of the eigen-vectors corresponding to the first $n_c$ eigenvalues of $\bar RA$ (with $\bar R=R+R^T-R^TAR$). We also 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 provide 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Error estimates for structure-preserving discretization of the incompressible MHD system

In this paper, we carry out the error analysis for the structure-preserving discretization of the incompressible MHD system. This system, as a coupled system of Navier-Stokes equations and Maxwell's equations, is nonlinear. We use its energy estimate and the underlying physical structure to facilitate the error analysis. Under certain CFL conditions, we prove the optimal order of convergence. To support the theoretical results, we also present numerical tests.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fast multilevel solvers for a class of discrete fourth order parabolic problems

In this paper, we study fast iterative solvers for the solution of fourth order parabolic equations discretized by mixed finite element methods. We propose to use consistent mass matrix in the discretization and use lumped mass matrix to construct efficient preconditioners. We provide eigenvalue analysis for the preconditioned system and estimate the convergence rate of the preconditioned GMRes method. Furthermore, we show that these preconditioners only need to be solved inexactly by optimal multigrid algorithms. Our numerical examples indicate that the proposed preconditioners are very efficient and robust with respect to both discretization parameters and diffusion coefficients. We also investigate the performance of multigrid algorithms with either collective smoothers or distributive smoothers when solving the preconditioner systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

High-Order Extended Finite Element Methods for Solving Interface Problems

In this paper, we study arbitrary order extended finite element (XFE) methods based on two discontinuous Galerkin (DG) schemes in order to solve elliptic interface problems in two and three dimensions. Optimal error estimates in the piecewise $H^1$-norm and in the $L^2$-norm are rigorously proved for both schemes. In particular, we have devised a new parameter-friendly DG-XFEM method, which means that no "sufficiently large" parameters are needed to ensure the optimal convergence of the scheme. To prove the stability of bilinear forms, we derive non-standard trace and inverse inequalities for high-order polynomials on curved sub-elements divided by the interface. All the estimates are independent of the location of the interface relative to the meshes. Numerical examples are given to support the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Energetically stable discretizations for charge carrier transport and electrokinetic models

A finite element discretization using a method of lines approached is proposed for approximately solving the Poisson-Nernst-Planck (PNP) equations. This discretization scheme enforces positivity of the computed solutions, corresponding to particle density functions, and a discrete energy estimate is established that resembles the familiar energy law for the PNP system. This energy estimate is extended to finite element solutions to an electrokinetic model, which couples the PNP system with the Navier-Stokes equations. Numerical experiments are conducted to validate convergence of the computed solution and verify the discrete energy estimate.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Modeling and Simulation for Fluid-Rotating Structure Interaction

In this paper, we study a dynamic fluid-structure interaction (FSI) model for an elastic structure that is immersed and spinning in the fluid. We develop a linear constitutive model to describe the motion of a rotational elastic structure which is suitable for the application of arbitrary Lagrangian-Eulerian (ALE) method in FSI simulation. Additionally, a novel ALE mapping method is designed to generate the moving fluid mesh while the deformable structure spins in a non-axisymmetric fluid channel. The structure velocity is adopted as the principle unknown to form a monolithic saddle-point system together with fluid velocity and pressure. We discretize the nonlinear saddle-point system with mixed finite element method and Newton's linearization, and prove that the derived saddle-point problem is well-posed. The developed methodology is applied to a self-defined elastic structure and a realistic hydro-turbine under a prescribed angular velocity. Both illustrate the satisfactory numerical results of an elastic structure that is deforming and rotating while interacting with the fluid. The numerical validation is also conducted to demonstrate the modeling consistency.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Robust Preconditioners for Incompressible MHD Models

In this paper, we develop two classes of robust preconditioners for the structure-preserving discretization of the incompressible magnetohydrodynamics (MHD) system. By studying the well-posedness of the discrete system, we design block preconditioners for them and carry out rigorous analysis on their performance. We prove that such preconditioners are robust with respect to most physical and discretization parameters. In our proof, we improve the existing estimates of the block triangular preconditioners for saddle point problems by removing the scaling parameters, which are usually difficult to choose in practice. This new technique is not only applicable to the MHD system, but also to other problems. Moreover, we prove that Krylov iterative methods with our preconditioners preserve the divergence-free condition exactly, which complements the structure-preserving discretization. Another feature is that we can directly generalize this technique to other discretizations of the MHD system. We also present preliminary numerical results to support the theoretical results and demonstrate the robustness of the proposed preconditioners.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Nearly Optimal Multigrid Method for General Unstructured Grids

In this paper, we develop a multigrid method on unstructured shape-regular grids. For a general shape-regular unstructured grid of ${\cal O}(N)$ elements, we present a construction of an auxiliary coarse grid hierarchy on which a geometric multigrid method can be applied together with a smoothing on the original grid by using the auxiliary space preconditioning technique. Such a construction is realized by a cluster tree which can be obtained in ${\cal O}(N\log N)$ operations for a grid of $N$ elements. This tree structure in turn is used for the definition of the grid hierarchy from coarse to fine. For the constructed grid hierarchy we prove that the convergence rate of the multigrid preconditioned CG for an elliptic PDE is $1 - {\cal O}({1}/{\log N})$. Numerical experiments confirm the theoretical bounds and show that the total complexity is in ${\cal O}(N\log N)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multilevel Preconditioners for Reaction-Diffusion Problems with Discontinuous Coefficients

In this paper, we extend some of the multilevel convergence results obtained by Xu and Zhu in [Xu and Zhu, M3AS 2008], to the case of second order linear reaction-diffusion equations. Specifically, we consider the multilevel preconditioners for solving the linear systems arising from the linear finite element approximation of the problem, where both diffusion and reaction coefficients are piecewise-constant functions. We discuss in detail the influence of both the discontinuous reaction and diffusion coefficients to the performance of the classical BPX and multigrid V-cycle preconditioners.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Stable Finite Element Methods Preserving $\nabla \cdot \boldsymbol{B} = 0$ Exactly for MHD Models

This paper is devoted to the design and analysis of some structure-preserving finite element schemes for the magnetohydrodynamics (MHD) system. The main feature of the method is that it naturally preserves the important Gauss law, namely $\nabla\cdot\boldsymbol{B}=0$. In contrast to most existing approaches that eliminate the electrical field variable $\boldsymbol{E}$ and give a direct discretization of the magnetic field, our new approach discretizes the electric field $\boldsymbol{E}$ by Nédélec type edge elements for $H(\mathrm{curl})$, while the magnetic field $\boldsymbol{B}$ by Raviart-Thomas type face elements for $H(\mathrm{div})$. As a result, the divergence-free condition on the magnetic field holds exactly on the discrete level. For this new finite element method, an energy stability estimate can be naturally established in an analogous way as in the continuous case. Furthermore, well-posedness is rigorously established in the paper for both the Picard and Newton linearization of the fully nonlinear systems by using the Brezzi theory for both the continuous and discrete cases. This well-posedness naturally leads to robust (and optimal) preconditioners for the linearized systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Error-Resilient Redundant Subspace Correction Method

As we stride toward the exascale era, due to increasing complexity of supercomputers, hard and soft errors are causing more and more problems in high-performance scientific and engineering computation. In order to improve reliability (increase the mean time to failure) of computing systems, a lot of efforts have been devoted to developing techniques to forecast, prevent, and recover from errors at different levels, including architecture, application, and algorithm. In this paper, we focus on algorithmic error resilient iterative linear solvers and introduce a redundant subspace correction method. Using a general framework of redundant subspace corrections, we construct iterative methods, which have the following properties: (1) Maintain convergence when error occurs assuming it is detectable; (2) Introduce low computational overhead when no error occurs; (3) Require only small amount of local (point-to-point) communication compared to traditional methods and maintain good load balance; (4) Improve the mean time to failure. With the proposed method, we can improve reliability of many scientific and engineering applications. Preliminary numerical experiments demonstrate the efficiency and effectiveness of the new subspace correction method.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Block Triangular Preconditioning for Stochastic Galerkin Method

In this paper we study fast iterative solvers for the large sparse linear systems resulting from the stochastic Galerkin discretization of stochastic partial differential equations. A block triangular preconditioner is introduced and applied to the Krylov subspace methods, including the generalized minimum residual method and the generalized preconditioned conjugate gradient method. This preconditioner utilizes the special structures of the stochastic Galerkin matrices to achieve high efficiency. Spectral bounds for the preconditioned matrix are provided for convergence analysis. The preconditioner system can be solved approximately by geometric multigrid V-cycle. Numerical results indicate that the block triangular preconditioner has better performance than the traditional block diagonal preconditioner for stochastic problems with large variance.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Combined Preconditioning with Applications in Reservoir Simulation

We develop a simple algorithmic framework to solve large-scale symmetric positive definite linear systems. At its core, the framework relies on two components: (1) a norm-convergent iterative method (i.e. smoother) and (2) a preconditioner. The resulting preconditioner, which we refer to as a combined preconditioner, is much more robust and efficient than the iterative method and preconditioner when used in Krylov subspace methods. We prove that the combined preconditioner is positive definite and show estimates on the condition number of the preconditioned system. We combine an algebraic multigrid method and an incomplete factorization preconditioner to test the proposed framework on problems in petroleum reservoir simulation. Our numerical experiments demonstrate noticeable speed-up when we compare our combined method with the standalone algebraic multigrid method or the incomplete factorization preconditioner.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Comparative Convergence Analysis of Nonlinear AMLI-cycle Multigrid

The main purpose of this paper is to provide a comprehensive convergence analysis of nonlinear AMLI-cycle multigrid method for symmetric positive definite problems. Based on classical assumptions for approximation and smoothing properties, we show that the nonlinear AMLI-cycle MG method is uniformly convergent. Furthermore, under only the assumption that the smoother is convergent, we show that the nonlinear AMLI-cycle method is always better (or not worse) than the respective V-cycle MG method. Finally, numerical experiments are presented to illustrate the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Convergence and optimality of the adaptive Morley element method

This paper is devoted to the convergence and optimality analysis of the adaptive Morley element method for the fourth order elliptic problem. A new technique is developed to establish a quasi-orthogonality which is crucial for the convergence analysis of the adaptive nonconforming method. By introducing a new parameter-dependent error estimator and further establishing a discrete reliability property, sharp convergence and optimality estimates are then fully proved for the fourth order elliptic problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Convergence and optimality of the adaptive nonconforming linear element method for the Stokes problem

In this paper, we analyze the convergence and optimality of a standard adaptive nonconforming linear element method for the Stokes problem. After establishing a special quasi--orthogonality property for both the velocity and the pressure in this saddle point problem, we introduce a new prolongation operator to carry through the discrete reliability analysis for the error estimator. We then use a specially defined interpolation operator to prove that, up to oscillation, the error can be bounded by the approximation error within a properly defined nonlinear approximate class. Finally, by introducing a new parameter-dependent error estimator, we prove the convergence and optimality estimates.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Numerical Study of Geometric Multigrid Methods on CPU--GPU Heterogeneous Computers

The geometric multigrid method (GMG) is one of the most efficient solving techniques for discrete algebraic systems arising from elliptic partial differential equations. GMG utilizes a hierarchy of grids or discretizations and reduces the error at a number of frequencies simultaneously. Graphics processing units (GPUs) have recently burst onto the scientific computing scene as a technology that has yielded substantial performance and energy-efficiency improvements. A central challenge in implementing GMG on GPUs, though, is that computational work on coarse levels cannot fully utilize the capacity of a GPU. In this work, we perform numerical studies of GMG on CPU--GPU heterogeneous computers. Furthermore, we compare our implementation with an efficient CPU implementation of GMG and with the most popular fast Poisson solver, Fast Fourier Transform, in the cuFFT library developed by NVIDIA.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Parallel Auxiliary Grid AMG Method for GPU

In this paper, we develop a new parallel auxiliary grid algebraic multigrid (AMG) method to leverage the power of graphic processing units (GPUs). In the construction of the hierarchical coarse grid, we use a simple and fixed coarsening procedure based on a region quadtree generated from an auxiliary grid. This allows us to explicitly control the sparsity patterns and operator complexities of the AMG solver. This feature provides (nearly) optimal load balancing and predictable communication patterns, which makes our new algorithm suitable for parallel computing, especially on GPU. We also design a parallel smoother based on the special coloring of the quadtree to accelerate the convergence rate and improve the parallel performance of this solver. Based on the CUDA toolkit [40], we implemented our new parallel auxiliary grid AMG method on GPU and the numerical results of this implementation demonstrate the efficiency of our new method. The results achieve an average speedup of over 4 on quasi-uniform grids and 2 on shape regular grids when compared to the AMG implementation in CUSP.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local Multilevel Preconditioners for Elliptic Equations with Jump Coefficients on Bisection Grids

The goal of this paper is to design optimal multilevel solvers for the finite element approximation of second order linear elliptic problems with piecewise constant coefficients on bisection grids. Local multigrid and BPX preconditioners are constructed based on local smoothing only at the newest vertices and their immediate neighbors. The analysis of eigenvalue distributions for these local multilevel preconditioned systems shows that there are only a fixed number of eigenvalues which are deteriorated by the large jump. The remaining eigenvalues are bounded uniformly with respect to the coefficients and the meshsize. Therefore, the resulting preconditioned conjugate gradient algorithm will converge with an asymptotic rate independent of the coefficients and logarithmically with respect to the meshsize. As a result, the overall computational complexity is nearly optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Adaptive Eulerian-Lagrangian Method for Linear Convection-Diffusion Problems

In this paper, we consider the adaptive Eulerian--Lagrangian method (ELM) for linear convection-diffusion problems. Unlike the classical a posteriori error estimations, we estimate the temporal error along the characteristics and derive a new a posteriori error bound for ELM semi-discretization. With the help of this proposed error bound, we are able to show the optimal convergence rate of ELM for solutions with minimal regularity. Furthermore, by combining this error bound with a standard residual-type estimator for the spatial error, we obtain a posteriori error estimators for a fully discrete scheme. We present numerical tests to demonstrate the efficiency and robustness of our adaptive algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal solvers for fourth-order PDEs discretized on unstructured grids

This paper provides the first provable $\mathcal{O}(N \log N)$ algorithms for the linear system arising from the direct finite element discretization of the fourth-order equation with different boundary conditions on unstructured grids of size $N$ on an arbitrary polygoanl domain. Several preconditioners are presented, and the conjugate gradient methods applied with these preconditioners are proven to converge uniformly with respect to the size of the preconditioned linear system. One main ingredient of the optimal preconditioners is a mixed-form discretization of the fourth-order problem. Such a mixed-form discretization leads to a non-desirable ---either non-optimal or non-convergent--- approximation of the original solution, but it provides optimal preconditioners for the direct finite element problem. It is further shown that the implementation of the preconditioners can be reduced to the solution of several discrete Poisson equations. Therefore, any existing optimal or nearly optimal solver, such as geometric or algebraic multigrid methods, for Poisson equations would lead to a nearly optimal solver for the discrete fourth-order system. A number of nonstandard Sobolev spaces and their discretizations defined on the boundary of polygonal domains are carefully studied and used for the analysis of those preconditioners.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Analysis of two-level method for anisotropic diffusion equations on aligned and non-aligned grids

This paper is devoted to the multigrid convergence analysis for the linear systems arising from the conforming linear finite element discretization of the second order elliptic equations with anisotropic diffusion. The multigrid convergence behavior is known to strongly depend on whether the discretization grid is aligned or non-aligned with the anisotropic direction and analyses in the paper will be mainly focused on two-level algorithms. For an aligned grid case, a lower bound is given for point-wise smoother which shows deterioration of convergence rate. In both aligned and non-aligned cases we show that for a specially designed block smoother the convergence is uniform with respect to both anisotropy ratio and mesh size in the energy norm. The analysis is complemented with numerical experiments which confirm the theoretical results

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Lower Bounds of the Discretization for Piecewise Polynomials

Assume that $V_h$ is a space of piecewise polynomials of degree less than $r\geq 1$ on a family of quasi-uniform triangulation of size $h$. Then the following well-known upper bound holds for a sufficiently smooth function $u$ and $p\in [1, \infty]$ $$ \inf_{v_h\in V_h}\|u-v_h\|_{j,p,Ω,h} \le C h^{r-j} |u|_{r,p,Ω},\quad 0\le j\le r. $$ In this paper, we prove that, roughly speaking, if $u\not\in V_h$, the above estimate is sharp. Namely, $$ \inf_{v_h\in V_h}\|u-v_h\|_{j,p,Ω,h} \ge c h^{r-j},\quad 0\le j\le r, \ \ 1\leq p\leq \infty, $$ for some $c>0$. The above result is further extended to various situations including more general Sobolev space norms, general shape regular grids and many different types of finite element spaces. As an application, the sharpness of finite element approximation of elliptic problems and the corresponding eigenvalue problems is established.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Nonconforming Finite Element Method for Fourth Order Curl Equations in R^3

In this paper we present a nonconforming finite element method for solving fourth order curl equations in three dimensions arising from magnetohydrodynamics models. We show that the method has an optimal error estimate for a model problem involving both curl^2 and curl^4 operators. The element has a very small number of degrees of freedom and it imposes the inter-element continuity along the tangential direction which is appropriate for the approximation of magnetic fields. We also provide explicit formulae of basis functions for this element.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Convergence and Optimality of Adaptive Mixed Finite Element Methods

The convergence and optimality of adaptive mixed finite element methods for the Poisson equation are established in this paper. The main difficulty for mixed finite element methods is the lack of minimization principle and thus the failure of orthogonality. A quasi-orthogonality property is proved using the fact that the error is orthogonal to the divergence free subspace, while the part of the error that is not divergence free can be bounded by the data oscillation using a discrete stability result. This discrete stability result is also used to get a localized discrete upper bound which is crucial for the proof of the optimality of the adaptive approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Finite Element Approximation of the Nonlinear Poisson-Boltzmann Equation

A widely used electrostatics model in the biomolecular modeling community, the nonlinear Poisson-Boltzmann equation, along with its finite element approximation, are analyzed in this paper. A regularized Poisson-Boltzmann equation is introduced as an auxiliary problem, making it possible to study the original nonlinear equation with delta distribution sources. A priori error estimates for the finite element approximation are obtained for the regularized Poisson-Boltzmann equation based on certain quasi-uniform grids in two and three dimensions. Adaptive finite element approximation through local refinement driven by an a posteriori error estimate is shown to converge. The Poisson-Boltzmann equation does not appear to have been previously studied in detail theoretically, and it is hoped that this paper will help provide molecular modelers with a better foundation for their analytical and computational work with the Poisson-Boltzmann equation. Note that this article apparently gives the first rigorous convergence result for a numerical discretization technique for the nonlinear Poisson-Boltzmann equation with delta distribution sources, and it also introduces the first provably convergent adaptive method for the equation. This last result is currently one of only a handful of existing convergence results of this type for nonlinear problems.

0 citations0 reviewsNo code linkedOpen access