A subspace shift technique for nonsymmetric algebraic Riccati equations associated with an M‐matrix

The worst situation in computing the minimal nonnegative solution of a nonsymmetric algebraic Riccati equation associated with an M‐matrix occurs when the corresponding linearizing matrix has two very small eigenvalues, one with positive and one with negative real part. When both eigenvalues are exactly zero, the problem is called critical or null recurrent. Although in this case the problem is ill‐conditioned and the convergence of the algorithms based on matrix iterations is slow, there exist some techniques to remove the singularity and transform the problem to a well‐behaved one. Ill‐conditioning and slow convergence appear also in close‐to‐critical problems, but when none of the eigenvalues is exactly zero, the techniques used for the critical case cannot be applied. In this paper, we introduce a new method to accelerate the convergence properties of the iterations also in close‐to‐critical cases, by working on the invariant subspace associated with the problematic eigenvalues as a whole. We present numerical experiments that confirm the efficiency of the new method.Copyright © 2012 John Wiley & Sons, Ltd.     

A structure‐preserving doubling algorithm for Lur'e equations

We introduce a numerical method for the numerical solution of the Lur'e equations, a system of matrix equations that arises, for instance, in linear‐quadratic infinite time horizon optimal control. We focus on small‐scale, dense problems. Via a Cayley transformation, the problem is transformed to the discrete‐time case, and the structural infinite eigenvalues of the associated matrix pencil are deflated. The deflated problem is associated with a symplectic pencil with several Jordan blocks of eigenvalue 1 and even size, which arise from the nontrivial Kronecker chains at infinity of the original problem. For the solution of this modified problem, we use the structure‐preserving doubling algorithm. Implementation issues such as the choice of the parameter γ in the Cayley transform are discussed. The most interesting feature of this method, with respect to the competing approaches, is the absence of arbitrary rank decisions, which may be ill‐posed and numerically troublesome. The numerical examples presented confirm the effectiveness of this method. Copyright © 2015 John Wiley & Sons, Ltd.     

On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

The double deflating technique for irreducible singular M-matrix algebraic Riccati equations in the critical case

As is known, Alternating-Directional Doubling Algorithm (ADDA) is quadratically convergent for computing the minimal nonnegative solution of an irreducible singular M-matrix algebraic Riccati equation (MARE) in the noncritical case or a nonsingular MARE, but ADDA is only linearly convergent in the critical case. The drawback can be overcome by deflating techniques for an irreducible singular MARE so that the speed of quadratic convergence is still preserved in the critical case and accelerated in the noncritical case. In this paper, we proposed an improved deflating technique to accelerate further the convergence speed – the double deflating technique for an irreducible singular MARE in the critical case. We proved that ADDA is quadratically convergent instead of linearly when it is applied to the deflated algebraic Riccati equation (ARE) obtained by a double deflating technique. We also showed that the double deflating technique is better than the deflating technique from the perspective of dimension of the deflated ARE. Numerical experiments are provided to illustrate that our double deflating technique is effective.     

Fast verified computation for solutions of algebraic Riccati equations arising in transport theory

A fast algorithm for enclosing the solution of the nonsymmetric algebraic Riccati equation arising in transport theory is proposed. The equation has a special structure, which is taken into account to reduce the complexity. By exploiting the structure, the enclosing process involves only quadratic complexity under a reasonable assumption. The algorithm moreover verifies the uniqueness and minimal positiveness of the enclosed solution. Numerical results show the efficiency of the algorithm.     

Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations

For the non‐symmetric algebraic Riccati equations, we establish a class of alternately linearized implicit (ALI) iteration methods for computing its minimal non‐negative solutions by technical combination of alternate splitting and successive approximating of the algebraic Riccati operators. These methods include one iteration parameter, and suitable choices of this parameter may result in fast convergent iteration methods. Under suitable conditions, we prove the monotone convergence and estimate the asymptotic convergence factor of the ALI iteration matrix sequences. Numerical experiments show that the ALI iteration methods are feasible and effective, and can outperform the Newton iteration method and the fixed‐point iteration methods. Besides, we further generalize the known fixed‐point iterations, obtaining an extensive class of relaxed splitting iteration methods for solving the non‐symmetric algebraic Riccati equations. Copyright © 2006 John Wiley & Sons, Ltd.     

Direct algorithm for the solution of two‐sided obstacle problems with M‐matrix

A direct algorithm for the solution to the affine two‐sided obstacle problem with an M‐matrix is presented. The algorithm has the polynomial bounded computational complexity O(n³) and is more efficient than those in (Numer. Linear Algebra Appl. 2006; 13 :543–551). Copyright © 2010 John Wiley & Sons, Ltd.     

Some predictor–corrector‐type iterative schemes for solving nonsymmetric algebraic Riccati equations arising in transport theory

It is as well known that nonsymmetric algebraic Riccati equations arising in transport theory can be translated to vector equations. In this paper, we propose six predictor–corrector‐type iterative schemes to solve the vector equations. And we give the convergence of these schemes. Unlike the previous work, we prove that all of them converge to the minimal positive solution of the vector equations by the initial vector (e,e), where e = (1,1, ? ,1)^T. Moreover, we prove that all the sequences generated by the iterative schemes are strictly and monotonically increasing and bounded above. In addition, some numerical results are also reported in the paper, which confirm the good theoretical properties of our approach. Copyright © 2014 John Wiley & Sons, Ltd.     

Convergence analysis of the Newton–Shamanskii method for a nonsymmetric algebraic Riccati equation

In this paper, we consider the nonsymmetric algebraic Riccati equation arising in transport theory. An important feature of this equation is that its minimal positive solution can be obtained via computing the minimal positive solution of a vector equation. We apply the Newton–Shamanskii method to solve the vector equation. Convergence analysis shows that the sequence of vectors generated by the Newton–Shamanskii method is monotonically increasing and converges to the minimal positive solution of the vector equation. Numerical experiments show that the Newton–Shamanskii method is feasible and effective, and outperforms the Newton method. Copyright © 2008 John Wiley & Sons, Ltd.     

A modified Newton method for solving non-symmetric algebraic Riccati equations arising in transport theory

Liang Bao ^{The non-symmetric algebraic Riccati equation arising in transporttheory can be rewritten as a vector equation and the minimalpositive solution of the non-symmetric algebraic Riccati equationcan be obtained by solving the vector equation. In this paper,we apply the modified Newton method to solve the vector equation.Some convergence results are presented. Numerical tests showthat the modified Newton method is feasible and effective, andoutperforms the Newton method.}     

Direct algorithms to solve the two‐sided obstacle problem for an M‐matrix

In this paper, two direct algorithms for solving the two‐sided obstacle problem with an M‐matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd.     

Efficient local structure‐preserving schemes for the RLW‐type equation

The multisymplectic schemes have been used in numerical simulations for the RLW‐type equation successfully. They well preserve the local geometric property, but not other local conservation laws. In this article, we propose three novel efficient local structure‐preserving schemes for the RLW‐type equation, which preserve the local energy exactly on any time‐space region and can produce richer information of the original problem. The schemes will be mass‐ and energy‐preserving as the equation is imposed on appropriate boundary conditions. Numerical experiments are presented to verify the efficiency and invariant‐preserving property of the schemes. Comparisons with the existing nonconservative schemes are made to show the behavior of the energy affects the behavior of the solution.© 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 1678–1691, 2017     

Efficient structure‐preserving schemes for good Boussinesq equation

The good Boussinesq equation is endowed with symplectic conservation law and energy conservation law. In this paper, some new highly efficient structure‐preserving methods for the good Boussinesq equation are proposed by improving the standard finite difference method (FDM). The new methods only use and calculate values at the odd (or even) nodes to reduce the computational cost. We call this kind of methods odd‐even method (OEM). Numerical results show that the OEM and the standard FDM have nearly the same numerical errors under the same mesh partition. However, the OEM is much more efficient than the standard FDM, such as the consumed CPU time and occupied memory.     

A vertex‐centered and positivity‐preserving scheme for anisotropic diffusion equations on general polyhedral meshes

We propose a new nonlinear positivity‐preserving finite volume scheme for anisotropic diffusion problems on general polyhedral meshes with possibly nonplanar faces. The scheme is a vertex‐centered one where the edge‐centered, face‐centered, and cell‐centered unknowns are treated as auxiliary ones that can be computed by simple second‐order and positivity‐preserving interpolation algorithms. Different from most existing positivity‐preserving schemes, the presented scheme is based on a special nonlinear two‐point flux approximation that has a fixed stencil and does not require the convex decomposition of the co‐normal. More interesting is that the flux discretization is actually performed on a fixed tetrahedral subcell of the primary cell, which makes the scheme very easy to be implemented on polyhedral meshes with star‐shaped cells. Moreover, it is suitable for polyhedral meshes with nonplanar faces, and it does not suffer the so‐called numerical heat‐barrier issue. The truncation error is analyzed rigorously, while the Picard method and its Anderson acceleration are used for the solution of the resulting nonlinear system. Numerical experiments are also provided to demonstrate the second‐order accuracy and well positivity of the numerical solution for heterogeneous and anisotropic diffusion problems on severely distorted grids.     

A numerical approach for solving weakly singular partial integro‐differential equations via two‐dimensional‐orthonormal Bernstein polynomials with the convergence analysis

In this paper, we develop an efficient matrix method based on two‐dimensional orthonormal Bernstein polynomials (2D‐OBPs) to provide approximate solution of linear and nonlinear weakly singular partial integro‐differential equations (PIDEs). First, we approximate all functions involved in the considerable problem via 2D‐OBPs. Then, by using the operational matrices of integration, differentiation, and product, the solution of Volterra singular PIDEs is transformed to the solution of a linear or nonlinear system of algebraic equations which can be solved via some suitable numerical methods. With a small number of bases, we can find a reasonable approximate solution. Moreover, we establish some useful theorems for discussing convergence analysis and obtaining an error estimate associated with the proposed method. Finally, we solve some illustrative examples by employing the presented method to show the validity, efficiency, high accuracy, and applicability of the proposed technique.     

A new approach by two‐dimensional wavelets operational matrix method for solving variable‐order fractional partial integro‐differential equations

In this paper, a new computational scheme based on operational matrices (OMs) of two‐dimensional wavelets is proposed for the solution of variable‐order (VO) fractional partial integro‐differential equations (PIDEs). To accomplish this method, first OMs of integration and VO fractional derivative (FD) have been derived using two‐dimensional Legendre wavelets. By implementing two‐dimensional wavelets approximations and the OMs of integration and variable‐order fractional derivative (VO‐FD) along with collocation points, the VO fractional partial PIDEs are reduced into the system of algebraic equations. In addition to this, some useful theorems are discussed to establish the convergence analysis and error estimate of the proposed numerical technique. Furthermore, computational efficiency and applicability are examined through some illustrative examples.     

A new look at the doubling algorithm for a structured palindromic quadratic eigenvalue problem

Recently, Guo and Lin [SIAM J. Matrix Anal. Appl., 31 (2010), 2784–2801] proposed an efficient numerical method to solve the palindromic quadratic eigenvalue problem (PQEP) (λ²A^T+λQ + A)z = 0 arising from the vibration analysis of high speed trains, where have special structures: both Q and A are, among others, m × m block matrices with each block being k × k (thus, n = mk), and moreover, Q is block tridiagonal, and A has only one nonzero block in the (1,m)th block position. The key intermediate step of the method is the computation of the so‐called stabilizing solution to the n × n nonlinear matrix equation X + A^TX⁻¹A = Q via the doubling algorithm. The aim of this article is to propose an improvement to this key step through solving a new nonlinear matrix equation having the same form but of only k × k in size. This new and much smaller matrix equation can also be solved by the doubling algorithm. For the same accuracy, it takes the same number of doubling iterations to solve both the larger and the new smaller matrix equations, but each doubling iterative step on the larger equation takes about 4.8 as many flops than the step on the smaller equation. Replacing Guo's and Lin's key intermediate step by our modified one leads to an alternative method for the PQEP. This alternative method is faster, but the improvement in speed is not as dramatic as just for solving the respective nonlinear matrix equations and levels off as m increases. Numerical examples are presented to show the effectiveness of the new method. Copyright © 2014 John Wiley & Sons, Ltd.     

A Jacobi–Davidson method for two‐real‐parameter nonlinear eigenvalue problems arising from delay‐differential equations

The critical delays of a delay‐differential equation can be computed by solving a nonlinear two‐parameter eigenvalue problem. The solution of this two‐parameter problem can be translated to solving a quadratic eigenvalue problem of squared dimension. We present a structure preserving QR‐type method for solving such quadratic eigenvalue problem that only computes real‐valued critical delays; that is, complex critical delays, which have no physical meaning, are discarded. For large‐scale problems, we propose new correction equations for a Newton‐type or Jacobi–Davidson style method, which also forces real‐valued critical delays. We present three different equations: one real‐valued equation using a direct linear system solver, one complex valued equation using a direct linear system solver, and one Jacobi–Davidson style correction equation that is suitable for an iterative linear system solver. We show numerical examples for large‐scale problems arising from PDEs. Copyright © 2012 John Wiley & Sons, Ltd.     

A geometric‐based algebraic multigrid method for higher‐order finite element equations in two‐dimensional linear elasticity

In this paper, we will discuss the geometric‐based algebraic multigrid (AMG) method for two‐dimensional linear elasticity problems discretized using quadratic and cubic elements. First, a two‐level method is proposed by analyzing the relationship between the linear finite element space and higher‐order finite element space. And then a geometric‐based AMG method is obtained with the existing solver used as a solver on the first coarse level. The resulting AMG method is applied to some typical elasticity problems including the plane strain problem with jumps in Young's modulus. The results of various numerical experiments show that the proposed AMG method is much more robust and efficient than a classical AMG solver that is applied directly to the high‐order systems alone. Moreover, we present the corresponding theoretical analysis for the convergence of the proposed AMG algorithms. These theoretical results are also confirmed by some numerical tests. Copyright © 2008 John Wiley & Sons, Ltd.     

Local energy‐ and momentum‐preserving schemes for Klein‐Gordon‐Schrödinger equations and convergence analysis

In this article, we obtain local energy and momentum conservation laws for the Klein‐Gordon‐Schrödinger equations, which are independent of the boundary condition and more essential than the global conservation laws. Based on the rule that the numerical methods should preserve the intrinsic properties as much as possible, we propose local energy‐ and momentum‐preserving schemes for the equations. The merit of the proposed schemes is that the local energy/momentum conservation law is conserved exactly in any time‐space region. With suitable boundary conditions, the schemes will be charge‐ and energy‐/momentum‐preserving. Nonlinear analysis shows LEP schemes are unconditionally stable and the numerical solutions converge to the exact solutions with order . The theoretical properties are verified by numerical experiments. © 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 1329–1351, 2017