In this paper, an important discovery has been found for nonconforming immersed finite element (IFE) methods using integral-value degrees of freedom for solving elliptic interface problems. We show that those IFE methods can only achieve suboptimal convergence rates (i.e., $O(h^{1/2})$ in the $H^1$ norm and $O(h)$ in the $L^2$ norm) if the tangential derivative of the exact solution and the jump of the coefficient are not zero on the interface. A nontrivial counter example is also provided to support our theoretical analysis. To recover the optimal convergence rates, we develop a new nonconforming IFE method with additional terms locally on interface edges. The unisolvence of IFE basis functions is proved on arbitrary triangles. Furthermore, we derive the optimal approximation capabilities of both the Crouzeix-Raviart and the rotated-$Q_1$ IFE spaces for interface problems with variable coefficients via a unified approach different from multipoint Taylor expansions. Finally, optimal error estimates in both $H^1$- and $L^2$- norms are proved and confirmed with numerical experiments.
相關內容
This paper introduces the Nystr\"om PCG algorithm for solving a symmetric positive-definite linear system. The algorithm applies the randomized Nystr\"om method to form a low-rank approximation of the matrix, which leads to an efficient preconditioner that can be deployed with the conjugate gradient algorithm. Theoretical analysis shows that preconditioned system has constant condition number as soon as the rank of the approximation is comparable with the number of effective degrees of freedom in the matrix. The paper also develops adaptive methods for achieving similar performance without knowledge of the effective dimension. Numerical tests show that Nystr\"om PCG can rapidly solve large linear systems that arise in data analysis problems, and it surpasses several competing methods from the literature.
We consider the numerical approximation of the inertial Landau-Lifshitz-Gilbert equation (iLLG), which describes the dynamics of the magnetization in ferromagnetic materials at subpicosecond time scales. We propose and analyze two fully discrete numerical schemes: The first method is based on a reformulation of the problem as a linear constrained variational formulation for the linear velocity. The second method exploits a reformulation of the problem as a first order system in time for the magnetization and the angular momentum. Both schemes are implicit, based on first-order finite elements, and generate approximations satisfying the unit-length constraint of iLLG at the vertices of the underlying mesh. For both methods, we prove convergence of the approximations towards a weak solution of the problem. Numerical experiments validate the theoretical results and show the applicability of the methods for the simulation of ultrafast magnetic processes.
Fully implicit Runge-Kutta (IRK) methods have many desirable properties as time integration schemes in terms of accuracy and stability, but high-order IRK methods are not commonly used in practice with numerical PDEs due to the difficulty of solving the stage equations. This paper introduces a theoretical and algorithmic preconditioning framework for solving the systems of equations that arise from IRK methods applied to linear numerical PDEs (without algebraic constraints). This framework also naturally applies to discontinuous Galerkin discretizations in time. Under quite general assumptions on the spatial discretization that yield stable time integration, the preconditioned operator is proven to have condition number bounded by a small, order-one constant, independent of the spatial mesh and time-step size, and with only weak dependence on number of stages/polynomial order; for example, the preconditioned operator for 10th-order Gauss IRK has condition number less than two, independent of the spatial discretization and time step. The new method can be used with arbitrary existing preconditioners for backward Euler-type time stepping schemes, and is amenable to the use of three-term recursion Krylov methods when the underlying spatial discretization is symmetric. The new method is demonstrated to be effective on various high-order finite-difference and finite-element discretizations of linear parabolic and hyperbolic problems, demonstrating fast, scalable solution of up to 10th order accuracy. The new method consistently outperforms existing block preconditioning approaches, and in several cases, the new method can achieve 4th-order accuracy using Gauss integration with roughly half the number of preconditioner applications and wallclock time as required using standard diagonally implicit RK methods.
In this paper, we derive improved a priori error estimates for families of hybridizable interior penalty discontinuous Galerkin (H-IP) methods using a variable penalty for second-order elliptic problems. The strategy is to use a penalization function of the form $\mathcal{O}(1/h^{1+\delta})$, where $h$ denotes the mesh size and $\delta$ is a user-dependent parameter. We then quantify its direct impact on the convergence analysis, namely, the (strong) consistency, discrete coercivity, and boundedness (with $h^{\delta}$-dependency), and we derive updated error estimates for both discrete energy- and $L^{2}$-norms. The originality of the error analysis relies specifically on the use of conforming interpolants of the exact solution. All theoretical results are supported by numerical evidence.
Identification of a linear time-invariant dynamical system from partial observations is a fundamental problem in control theory. Particularly challenging are systems exhibiting long-term memory. A natural question is how learn such systems with non-asymptotic statistical rates depending on the inherent dimensionality (order) $d$ of the system, rather than on the possibly much larger memory length. We propose an algorithm that given a single trajectory of length $T$ with gaussian observation noise, learns the system with a near-optimal rate of $\widetilde O\left(\sqrt\frac{d}{T}\right)$ in $\mathcal{H}_2$ error, with only logarithmic, rather than polynomial dependence on memory length. We also give bounds under process noise and improved bounds for learning a realization of the system. Our algorithm is based on multi-scale low-rank approximation: SVD applied to Hankel matrices of geometrically increasing sizes. Our analysis relies on careful application of concentration bounds on the Fourier domain -- we give sharper concentration bounds for sample covariance of correlated inputs and for $\mathcal H_\infty$ norm estimation, which may be of independent interest.
The total variation diminishing (TVD) property is an important tool for ensuring nonlinear stability and convergence of numerical solutions of one-dimensional scalar conservation laws. However, it proved to be challenging to extend this approach to two-dimensional problems. Using the anisotropic definition for discrete total variation (TV), it was shown in \cite{Goodman} that TVD solutions of two-dimensional hyperbolic equations are at most first order accurate. We propose to use an alternative definition resulting from a full discretization of the semi-discrete Raviart-Thomas TV. We demonstrate numerically using the second order discontinuous Galerkin method that limited solutions of two-dimensional hyperbolic equations are TVD in means when total variation is computed using the new definition.
Block coordinate descent (BCD), also known as nonlinear Gauss-Seidel, is a simple iterative algorithm for nonconvex optimization that sequentially minimizes the objective function in each block coordinate while the other coordinates are held fixed. We propose a version of BCD that, for block multi-convex and smooth objective functions under constraints, is guaranteed to converge to the stationary points with worst-case rate of convergence of $O((\log n)^{2}/n)$ for $n$ iterations, and a bound of $O(\epsilon^{-1}(\log \epsilon^{-1})^{2})$ for the number of iterations to achieve an $\epsilon$-approximate stationary point. Furthermore, we show that these results continue to hold even when the convex sub-problems are inexactly solved if the optimality gaps are uniformly summable against initialization. A key idea is to restrict the parameter search within a diminishing radius to promote stability of iterates. As an application, we provide an alternating least squares algorithm with diminishing radius for nonnegative CP tensor decomposition that converges to the stationary points of the reconstruction error with the same robust worst-case convergence rate and complexity bounds. We also experimentally validate our results with both synthetic and real-world data and demonstrate that using auxiliary search radius restriction can in fact improve the rate of convergence.
This paper is concerned with the optimized Schwarz waveform relaxation method and Ventcel transmission conditions for the linear advection-diffusion equation. A mixed formulation is considered in which the flux variable represents both diffusive and advective flux, and Lagrange multipliers are introduced on the interfaces between nonoverlapping subdomains to handle tangential derivatives in the Ventcel conditions. A space-time interface problem is formulated and is solved iteratively. Each iteration involves the solution of time-dependent problems with Ventcel boundary conditions in the subdomains. The subdomain problems are discretized in space by a mixed hybrid finite element method based on the lowest-order Raviart-Thomas space and in time by the backward Euler method. The proposed algorithm is fully implicit and enables different time steps in the subdomains. Numerical results with discontinuous coefficients and various Pecl\'et numbers validate the accuracy of the method with nonconforming time grids and confirm the improved convergence properties of Ventcel conditions over Robin conditions.
This paper is concerned with numerical solution of transport problems in heterogeneous porous media. A semi-discrete continuous-in-time formulation of the linear advection-diffusion equation is obtained by using a mixed hybrid finite element method, in which the flux variable represents both the advective and diffusive flux, and the Lagrange multiplier arising from the hybridization is used for the discretization of the advective term. Based on global-in-time and nonoverlapping domain decomposition, we propose two implicit local time-stepping methods to solve the semi-discrete problem. The first method uses the time-dependent Steklov-Poincar\'e type operator and the second uses the optimized Schwarz waveform relaxation (OSWR) with Robin transmission conditions. For each method, we formulate a space-time interface problem which is solved iteratively. Each iteration involves solving the subdomain problems independently and globally in time; thus, different time steps can be used in the subdomains. The convergence of the fully discrete OSWR algorithm with nonmatching time grids is proved. Numerical results for problems with various Pecl\'et numbers and discontinuous coefficients, including a prototype for the simulation of the underground storage of nuclear waste, are presented to illustrate the performance of the proposed local time-stepping methods.
Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show that this is not the case for a class of large-scale problems trained with first-order methods including random least squares and one-hidden layer neural networks with random weights. In fact, the halting time exhibits a universality property: it is independent of the probability distribution. With this barrier for average-case analysis removed, we provide the first explicit average-case convergence rates showing a tighter complexity not captured by traditional worst-case analysis. Finally, numerical simulations suggest this universality property holds for a more general class of algorithms and problems.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191