The doubling algorithms are very efficient iterative methods for computing the unique minimal nonnegative solution to an M-matrix algebraic Riccati equation (MARE). They are globally and quadratically convergent, except for MARE in the critical case where convergence is linear with the linear rate 1/2. However, the initialization phase and the doubling iteration kernel of any doubling algorithm involve inverting nonsingular M-matrices. In particular, for MARE in the critical case, the M-matrices in the doubling iteration kernel, although nonsingular, move towards singular M-matrices at convergence. These inversions are causes of concerns on entrywise relative accuracy of the eventually computed minimal nonnegative solution. Fortunately, a nonsingular M-matrix can be inverted by the GTH-like algorithm of Alfa, Xue, and Ye [Math. Comp., 71:217--236, 2002] to almost full entrywise relative accuracy, provided a triplet representation of the matrix is known. Recently, Nguyen and Poloni [Numer. Math., 130(4):763--792, 2015] discovered a way to construct triplet representations in a cancellation-free manner for all involved M-matrices in the doubling iteration kernel, for a special class of MAREs arising from Markov-modulated fluid queues. In this paper, we extend Nguyen's and Poloni's work to all MAREs by also devising a way to construct the triplet representations cancellation-free. Our construction, however, is not a straightforward extension of theirs. It is made possible by an introduction of novel recursively computable auxiliary nonnegative vectors. As the second contribution, we propose an entrywise relative residual for an approximate solution. The residual has an appealing feature of being able to reveal the entrywise relative accuracies of all entries, large and small, of the approximation. This is in marked contrast to the usual legacy normalized residual which reflects relative accuracies of large entries well but not so much those of very tiny entries. Numerical examples are presented to demonstrate and confirm our claims.

The goal of this paper is to develop a novel semi-implicit spectral deferred correction (SDC) time marching method. The method can be used in a large class of problems, especially for highly nonlinear ordinary differential equations (ODEs) without easily separating of stiff and non-stiff components, which is more general and efficient comparing with traditional semi-implicit SDC methods. The proposed semi-implicit SDC method is based on low order time integration methods and corrected iteratively. The order of accuracy is increased for each additional iteration. And we also explore its local truncation error analytically. This SDC method is intended to be combined with the method of lines, which provides a flexible framework to develop high order semi-implicit time marching methods for nonlinear partial differential equations (PDEs). In this paper we mainly focus on the applications of the nonlinear PDEs with higher order spatial derivatives, e.g. convection diffusion equation, the surface diffusion and Willmore flow of graphs, the Cahn– Hilliard equation, the Cahn–Hilliard–Brinkman system and the phase field crystal equation. Coupled with the local discontinuous Galerkin (LDG) spatial discretization, the fully discrete schemes are all high order accurate in both space and time, and stable numerically with the time step proportional to the spatial mesh size. Numerical experiments are carried out to illustrate the accuracy and capability of the proposed semi-implicit SDC method.

No abstract uploaded!

We construct a counterexample to the conjugacy of maximal abelian diagonalizable subalgebras in extended affine Lie algebras.

We introduce two exponential-type integrators for the “good” Boussinesq equation. They are of orders one and two, respectively, and they require lower spatial regularity of the solution compared to classical exponential integrators. For the first integrator, we prove first-order convergence in H^r for solutions in H^{r+1} with r>1/2. This new integrator even converges (with lower order) in H^r for solutions in H^r, i.e., without any additional smoothness assumptions. For the second integrator, we prove second-order convergence in H^r for solutions in H^{r+3} with r>1/2 and convergence in L^2 for solutions in H^3. Numerical results are reported to illustrate the established error estimates. The experiments clearly demonstrate that the new exponential-type integrators are favorable over classical exponential integrators for initial data with low regularity.