We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solut ion over a more restricted monoid exists. As a corollary, we obtain a complexity classification for the same problem over groups.
相關內容
The construction of modified equations is an important step in the backward error analysis of symplectic integrator for Hamiltonian systems. In the context of partial differential equations, the standard construction leads to modified equations with increasingly high frequencies which increase the regularity requirements on the analysis. In this paper, we consider the next order modified equations for the implicit midpoint rule applied to the semilinear wave equation to give a proof-of-concept of a new construction which works directly with the variational principle. We show that a carefully chosen change of coordinates yields a modified system which inherits its analytical properties from the original wave equation. Our method systematically exploits additional degrees of freedom by modifying the symplectic structure and the Hamiltonian together.
We consider the cubic nonlinear Schr\"odinger equation with a spatially rough potential, a key equation in the mathematical setup for nonlinear Anderson localization. Our study comprises two main parts: new optimal results on the well-posedness analysis on the PDE level, and subsequently a new efficient numerical method, its convergence analysis and simulations that illustrate our analytical results. In the analysis part, our results focus on understanding how the regularity of the solution is influenced by the regularity of the potential, where we provide quantitative and explicit characterizations. Ill-posedness results are also established to demonstrate the sharpness of the obtained regularity characterizations and to indicate the minimum regularity required from the potential for the NLS to be solvable. Building upon the obtained regularity results, we design an appropriate numerical discretization for the model and establish its convergence with an optimal error bound. The numerical experiments in the end not only verify the theoretical regularity results, but also confirm the established convergence rate of the proposed scheme. Additionally, a comparison with other existing schemes is conducted to demonstrate the better accuracy of our new scheme in the case of a rough potential.
We investigate a second-order accurate time-stepping scheme for solving a time-fractional diffusion equation with a Caputo derivative of order~$\alpha \in (0,1)$. The basic idea of our scheme is based on local integration followed by linear interpolation. It reduces to the standard Crank--Nicolson scheme in the classical diffusion case, that is, as $\alpha\to 1$. Using a novel approach, we show that the proposed scheme is $\alpha$-robust and second-order accurate in the $L^2(L^2)$-norm, assuming a suitable time-graded mesh. For completeness, we use the Galerkin finite element method for the spatial discretization and discuss the error analysis under reasonable regularity assumptions on the given data. Some numerical results are presented at the end.
We present a full space-time numerical solution of the advection-diffusion equation using a continuous Galerkin finite element method. The Galerkin/least-square method is employed to ensure stability of the discrete variational problem. In the full space-time formulation, time is considered another dimension, and the time derivative is interpreted as an additional advection term of the field variable. We derive a priori error estimates and illustrate spatio-temporal convergence with several numerical examples. We also derive a posteriori error estimates, which coupled with adaptive space-time mesh refinement provide efficient and accurate solutions. The accuracy of the space-time solutions is illustrated against analytical solutions as well as against numerical solutions using a conventional time-marching algorithm.
We deal with an initial-boundary value problem for the multidimensional acoustic wave equation, with the variable speed of sound. For a three-level semi-explicit in time higher-order vector compact scheme, we prove stability and derive 4th order error bound in the enlarged energy norm. This scheme is three-point in each spatial direction, and it exploits additional sought functions which approximate 2nd order non-mixed spatial derivatives of the solution to the equation. At the first time level, a similar two-level in time scheme is applied, with no derivatives of the data. No iterations are required to implement the scheme. We also present results of various 3D numerical experiments that demonstrate a very high accuracy of the scheme for smooth data, its advantages in the error behavior over the classical explicit 2nd order scheme for nonsmooth data as well and an example of the wave in a layered medium initiated by the Ricker-type wavelet source function.
This study introduces the divergence-conforming discontinuous Galerkin finite element method (DGFEM) for numerically approximating optimal control problems with distributed constraints, specifically those governed by stationary generalized Oseen equations. We provide optimal a priori error estimates in energy norms for such problems using the divergence-conforming DGFEM approach. Moreover, we thoroughly analyze $L^2$ error estimates for scenarios dominated by diffusion and convection. Additionally, we establish the new reliable and efficient a posteriori error estimators for the optimal control of the Oseen equation with variable viscosity. Theoretical findings are validated through numerical experiments conducted in both two and three dimensions.
This paper is concerned with structure-preserving numerical approximations for a class of nonlinear nonlocal Fokker-Planck equations, which admit a gradient flow structure and find application in diverse contexts. The solutions, representing density distributions, must be non-negative and satisfy a specific energy dissipation law. We design an arbitrary high-order discontinuous Galerkin (DG) method tailored for these model problems. Both semi-discrete and fully discrete schemes are shown to admit the energy dissipation law for non-negative numerical solutions. To ensure the preservation of positivity in cell averages at all time steps, we introduce a local flux correction applied to the DDG diffusive flux. Subsequently, a hybrid algorithm is presented, utilizing a positivity-preserving limiter, to generate positive and energy-dissipating solutions. Numerical examples are provided to showcase the high resolution of the numerical solutions and the verified properties of the DG schemes.
We consider the equilibrium equations for a linearized Cosserat material. We identify their structure in terms of a differential complex, which is isomorphic to six copies of the de Rham complex through an algebraic isomorphism. Moreover, we show how the Cosserat materials can be analyzed by inheriting results from linearized elasticity. Both perspectives give rise to mixed finite element methods, which we refer to as strongly and weaky coupled, respectively. We prove convergence of both classes of methods, with particular attention to improved convergence rate estimates, and stability in the limit of vanishing Cosserat material parameters. The theoretical results are fully reflected in the actual performance of the methods, as shown by the numerical verifications.
We consider a family of conforming space-time finite element discretizations for the wave equation based on splines of maximal regularity in time. Traditional techniques may require a CFL condition to guarantee stability. Recent works by O. Steinbach and M. Zank (2018), and S. Fraschini, G. Loli, A. Moiola, and G. Sangalli (2023), have introduced unconditionally stable schemes by adding non-consistent penalty terms to the underlying bilinear form. Stability and error analysis have been carried out for lowest order discrete spaces. While higher order methods have shown promising properties through numerical testing, their rigorous analysis was still missing. In this paper, we address this stability analysis by studying the properties of the condition number of a family of matrices associated with the time discretization. For each spline order, we derive explicit estimates of both the CFL condition required in the unstabilized case and the penalty term that minimises the consistency error in the stabilized case. Numerical tests confirm the sharpness of our results.
For the Euler scheme of the stochastic linear evolution equations, discrete stochastic maximal $ L^p $-regularity estimate is established, and a sharp error estimate in the norm $ \|\cdot\|_{L^p((0,T)\times\Omega;L^q(\mathcal O))} $, $ p,q \in [2,\infty) $, is derived via a duality argument.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191