It is well known that the discretization of fractional diffusion equations (FDEs) with fractional derivatives $\alpha\in(1,2)$, using the so-called weighted and shifted Gr\"unwald formula, leads to linear systems whose coefficient matrices show a Toeplitz-like structure. More precisely, in the case of variable coefficients, the related matrix sequences belong to the so-called Generalized Locally Toeplitz (GLT) class. Conversely, when the given FDE have constant coefficients, using a suitable discretization, we encounter a Toeplitz structure associated to a nonnegative function $\mathcal{F}_\alpha$, called the spectral symbol, having a unique zero at zero of real positive order between one and two. For the fast solution of such systems by preconditioned Krylov methods, several preconditioning techniques have been proposed in both the one and two dimensional cases. In this note we propose a new preconditioner denoted by $\mathcal{P}_{\mathcal{F}_\alpha}$ which belongs to the $\tau$ algebra and it is based on the spectral symbol $\mathcal{F}_\alpha$. Comparing with some of the previously proposed preconditioners, we show that although the low band structure preserving preconditioners are more effective in the one-dimensional case, the new preconditioner performs better in the more challenging multi-dimensional setting.
相關內容
Like most multiobjective combinatorial optimization problems, biobjective optimization problems on matroids are in general intractable and their corresponding decision problems are in general NP-hard. In this paper, we consider biobjective optimization problems on matroids where one of the objective functions is restricted to binary cost coefficients. We show that in this case the problem has a connected efficient set with respect to a natural definition of a neighborhood structure and hence, can be solved efficiently using a neighborhood search approach. This is, to the best of our knowledge, the first non-trivial problem on matroids where connectedness of the efficient set can be established. The theoretical results are validated by numerical experiments with biobjective minimum spanning tree problems (graphic matroids) and with biobjective knapsack problems with a cardinality constraint (uniform matroids). In the context of the minimum spanning tree problem, coloring all edges with cost 0 green and all edges with cost 1 red leads to an equivalent problem where we want to simultaneously minimize one general objective and the number of red edges (which defines the second objective) in a Pareto sense.
In this paper, we study ideals spanned by polynomials or overconvergent series in a Tate algebra. With state-of-the-art algorithms for computing Tate Gr{\"o}bner bases, even if the input is polynomials, the size of the output grows with the required precision, both in terms of the size of the coefficients and the size of the support of the series. We prove that ideals which are spanned by polynomials admit a Tate Gr{\"o}bner basis made of polynomials, and we propose an algorithm, leveraging Mora's weak normal form algorithm, for computing it. As a result, the size of the output of this algorithm grows linearly with the precision. Following the same ideas, we propose an algorithm which computes an overconvergent basis for an ideal spanned by overconvergent series. Finally, we prove the existence of a universal analytic Gr{\"o}bner basis for polynomial ideals in Tate algebras, compatible with all convergence radii.
In distributional reinforcement learning not only expected returns but the complete return distributions of a policy are taken into account. The return distribution for a fixed policy is given as the solution of an associated distributional Bellman equation. In this note we consider general distributional Bellman equations and study existence and uniqueness of their solutions as well as tail properties of return distributions. We give necessary and sufficient conditions for existence and uniqueness of return distributions and identify cases of regular variation. We link distributional Bellman equations to multivariate affine distributional equations. We show that any solution of a distributional Bellman equation can be obtained as the vector of marginal laws of a solution to a multivariate affine distributional equation. This makes the general theory of such equations applicable to the distributional reinforcement learning setting.
A key advantage of isogeometric discretizations is their accurate and well-behaved eigenfrequencies and eigenmodes. For degree two and higher, however, optical branches of spurious outlier frequencies and modes may appear due to boundaries or reduced continuity at patch interfaces. In this paper, we introduce a variational approach based on perturbed eigenvalue analysis that eliminates outlier frequencies without negatively affecting the accuracy in the remainder of the spectrum and modes. We then propose a pragmatic iterative procedure that estimates the perturbation parameters in such a way that the outlier frequencies are effectively reduced. We demonstrate that our approach allows for a much larger critical time-step size in explicit dynamics calculations. In addition, we show that the critical time-step size obtained with the proposed approach does not depend on the polynomial degree of spline basis functions.
We derive bounds on the eigenvalues of a generic form of double saddle-point matrices. 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 experiments validate our analytical findings.
The aim of this work is to devise and analyse an accurate numerical scheme to solve Erd\'elyi-Kober fractional diffusion equation. This solution can be thought as the marginal pdf of the stochastic process called the generalized grey Brownian motion (ggBm). The ggBm includes some well-known stochastic processes: Brownian motion, fractional Brownian motion and grey Brownian motion. To obtain convergent numerical scheme we transform the fractional diffusion equation into its weak form and apply the discretization of the Erd\'elyi-Kober fractional derivative. We prove the stability of the solution of the semi-discrete problem and its convergence to the exact solution. Due to the singular in time term appearing in the main equation the proposed method converges slower than first order. Finally, we provide the numerical analysis of the full-discrete problem using orthogonal expansion in terms of Hermite functions.
Triangular decomposition with different properties has been used for various types of problem solving, e.g. geometry theorem proving, real solution isolation of zero-dimensional polynomial systems, etc. In this paper, the concepts of strong chain and square-free strong triangular decomposition (SFSTD) of zero-dimensional polynomial systems are defined. Because of its good properties, SFSTD may be a key way to many problems related to zero-dimensional polynomial systems, such as real solution isolation and computing radicals of zero-dimensional ideals. Inspired by the work of Wang and of Dong and Mou, we propose an algorithm for computing SFSTD based on Gr\"obner bases computation. The novelty of the algorithm is that we make use of saturated ideals and separant to ensure that the zero sets of any two strong chains have no intersection and every strong chain is square-free, respectively. On one hand, we prove that the arithmetic complexity of the new algorithm can be single exponential in the square of the number of variables, which seems to be among the rare complexity analysis results for triangular-decomposition methods. On the other hand, we show experimentally that, on a large number of examples in the literature, the new algorithm is far more efficient than a popular triangular-decomposition method based on pseudo-division. Furthermore, it is also shown that, on those examples, the methods based on SFSTD for real solution isolation and for computing radicals of zero-dimensional ideals are very efficient.
We develop a novel a posteriori error estimator for the L2 error committed by the finite element discretization of the solution of the fractional Laplacian. Our a posteriori error estimator takes advantage of the semi-discretization scheme using a rational approximation which allows to reformulate the fractional problem into a family of non-fractional parametric problems. The estimator involves applying the implicit Bank-Weiser error estimation strategy to each parametric non-fractional problem and reconstructing the fractional error through the same rational approximation used to compute the solution to the original fractional problem. We provide several numerical examples in both two and three-dimensions demonstrating the effectivity of our estimator for varying fractional powers and its ability to drive an adaptive mesh refinement strategy.
Physical systems are usually modeled by differential equations, but solving these differential equations analytically is often intractable. Instead, the differential equations can be solved numerically by discretization in a finite computational domain. The discretized equation is reduced to a large linear system, whose solution is typically found using an iterative solver. We start with an initial guess, x_0, and iterate the algorithm to obtain a sequence of solution vectors, x_m. The iterative algorithm is said to converge to solution $x$ if and only if x_m converges to $x$. Accuracy of the numerical solutions is important, especially in the design of safety critical systems such as airplanes, cars, or nuclear power plants. It is therefore important to formally guarantee that the iterative solvers converge to the "true" solution of the original differential equation. In this paper, we first formalize the necessary and sufficient conditions for iterative convergence in the Coq proof assistant. We then extend this result to two classical iterative methods: Gauss-Seidel iteration and Jacobi iteration. We formalize conditions for the convergence of the Gauss--Seidel classical iterative method, based on positive definiteness of the iterative matrix. We then formally state conditions for convergence of Jacobi iteration and instantiate it with an example to demonstrate convergence of iterative solutions to the direct solution of the linear system. We leverage recent developments of the Coq linear algebra and mathcomp library for our formalization.
The first focus of this paper is the characterization of the spectrum and the singular values of the coefficient matrix stemming from the discretization with space-time grid for a parabolic diffusion problem and from the approximation of distributed order fractional equations. For this purpose we will use the classical GLT theory and the new concept of GLT momentary symbols. The first permits to describe the singular value or eigenvalue asymptotic distribution of the sequence of the coefficient matrices, the latter permits to derive a function, which describes the singular value or eigenvalue distribution of the matrix of the sequence, even for small matrix-sizes but under given assumptions. The note is concluded with a list of open problems, including the use of our machinery in the study of iteration matrices, especially those concerning multigrid-type techniques.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191