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.     

Two‐level additive Schwarz algorithms for nonlinear complementarity problem with an M‐function

Nonlinear complementarity problem (NCP) is a wide class of problems. In this paper, some two‐level additive Schwarz algorithms for NCPs with an M‐function are developed and analyzed. The algorithms are proved to be convergent monotonically and can reach the solution of the problem within finite steps. They may also offer a possibility of making use of fast nonlinear solvers for solving the subproblems involved in the algorithms. Some preliminary numerical results are reported. Copyright © 2009 John Wiley & Sons, Ltd.     

A new two‐phase structure‐preserving doubling algorithm for critically singular M‐matrix algebraic Riccati equations

Among numerous iterative methods for solving the minimal nonnegative solution of an M‐matrix algebraic Riccati equation, the structure‐preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank‐one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank‐one component can be accurately recovered. We then propose an efficient hybrid method, called the two‐phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two‐phase SDA saves those SDA iterative steps that previously have to have for the rank‐one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two‐phase SDA. Copyright © 2015 John Wiley & Sons, Ltd.     

Some new properties of asynchronous algorithms of theta scheme combined with finite elements methods for an evolutionary implicit 2‐sided obstacle problem

In this paper, we give some new properties of the presented asynchronous algorithms of theta scheme combined with finite elements methods (App. Math. Comp., 217 (2011), 6443‐6450) for an evolutionary implicit 2‐sided obstacle problem to prove the existence and uniqueness of the discrete solution. Furthermore, an error estimate on the uniform norm is given.     

Tuned preconditioners for inexact two‐sided inverse and Rayleigh quotient iteration

Convergence results are provided for inexact two‐sided inverse and Rayleigh quotient iteration, which extend the previously established results to the generalized non‐Hermitian eigenproblem and inexact solves with a decreasing solve tolerance. Moreover, the simultaneous solution of the forward and adjoint problem arising in two‐sided methods is considered, and the successful tuning strategy for preconditioners is extended to two‐sided methods, creating a novel way of preconditioning two‐sided algorithms. Furthermore, it is shown that inexact two‐sided Rayleigh quotient iteration and the inexact two‐sided Jacobi‐Davidson method (without subspace expansion) applied to the generalized preconditioned eigenvalue problem are equivalent when a certain number of steps of a Petrov–Galerkin–Krylov method is used and when this specific tuning strategy is applied. Copyright © 2014 John Wiley & Sons, Ltd.     

On the M‐essential spectra of two‐group transport equations

In this paper, we deal with the M‐essential spectra of unbounded linear operators in Banach spaces where some generalizations of earlier work are given. Furthermore, we give an application from transport theory. Copyright © 2013 John Wiley & Sons, Ltd.     

Comparison of two algorithms for solving a two‐stage bilinear stochastic programming problem with quantile criterion

The paper is devoted to solving the two‐stage problem of stochastic programming with quantile criterion. It is assumed that the loss function is bilinear in random parameters and strategies, and the random vector has a normal distribution. Two algorithms are suggested to solve the problem, and they are compared. The first algorithm is based on the reduction of the original stochastic problem to a mixed integer linear programming problem. The second algorithm is based on the reduction of the problem to a sequence of convex programming problems. Performance characteristics of both the algorithms are illustrated by an example. A modification of both the algorithms is suggested to reduce the computing time. The new algorithm uses the solution obtained by the second algorithm as a starting point for the first algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

Direct pseudo‐spectral method for optimal control of obstacle problem – an optimal control problem governed by elliptic variational inequality

In this paper, a computational technique based on the pseudo‐spectral method is presented for the solution of the optimal control problem constrained with elliptic variational inequality. In fact, our aim in this paper is to present a direct approach for this class of optimal control problems. By using the pseudo‐spectral method, the infinite dimensional mathematical programming with equilibrium constraint, which can be an equivalent form of the considered problem, is converted to a finite dimensional mathematical programming with complementarity constraint. Then, the finite dimensional problem can be solved by the well‐developed methods. Finally, numerical examples are presented to show the validity and efficiency of the technique. Copyright © 2017 John Wiley & Sons, Ltd.     

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.     

One‐level and two‐level finite element methods for the Boussinesq problem

Previous works on the convergence of numerical methods for the Boussinesq problem were conducted, while the optimal L²‐norm error estimates for the velocity and temperature are still lacked. In this paper, the backward Euler scheme is used to discrete the time terms, standard Galerkin finite element method is adopted to approximate the variables. The MINI element is used to approximate the velocity and pressure, the temperature field is simulated by the linear polynomial. Under some restriction on the time step, we firstly present the optimal L² error estimates of approximate solutions. Secondly, two‐level method based on Stokes iteration for the Boussinesq problem is developed and the corresponding convergence results are presented. By this method, the original problem is decoupled into two small linear subproblems. Compared with the standard Galerkin method, the two‐level method not only keeps good accuracy but also saves a lot of computational cost. Finally, some numerical examples are provided to support the established theoretical analysis.     

Existence and stability of traveling wave solutions to one‐sided mixed initial‐boundary value problem for first‐order quasilinear hyperbolic systems

When one characteristic of the system is linearly degenerate, under suitable boundary conditions, we get the existence of traveling wave solutions located on the corresponding characteristic trajectory to the one‐sided mixed initial‐boundary value problem. When the system is linearly degenerate, by introducing the semi‐global normalized coordinates, we derive the related formulas of wave decomposition to prove the stability of traveling wave solutions corresponding to all leftward and the rightmost characteristic trajectories. Finally, for the traveling wave solutions corresponding to other rightward characteristic trajectories, some examples show their possible instability. Copyright © 2014 John Wiley & Sons, Ltd.     

GAUSSIAN PIVOTING METHOD FORSOLVING LINEAR COMPLEMENTARITY PROBLEM

In this paper, a new direct algorithm for solving linear complementarity problem with Z-matrix is proposed. The algorithm exhibits either a solution or its nonexistence after at most n steps (where n is the dimension of the problem) and the computational complexity is at most 1/3n^2 O(n^2)     

On the Cauchy problem for the two‐component b‐family system

In this paper, we establish the local well‐posedness for the two‐component b‐family system in a range of the Besov space. We also derive the blow‐up scenario for strong solutions of the system. In addition, we determine the wave‐breaking mechanism to the two‐component Dullin–Gottwald–Holm system. Copyright © 2013 John Wiley & Sons, Ltd.     

An approach for solving an inverse spherical two‐phase Stefan problem arising in modeling of electric contact phenomena

In this paper, a model problem that can be used for mathematical modeling and investigation of arc phenomena in electrical contacts is considered. An analytical approach for the solution of a two‐phase inverse spherical Stefan problem where along with unknown temperature functions heat flux function has to be determined is presented. The suggested solution method is obtained from a new form of integral error function and its properties that are represented in the form of series whose coefficients have to be determined. Using integral error function and collocation method, the solution of a test problem is obtained in exact form and approximately.     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Finding off‐diagonal entries of the inverse of a large symmetric sparse matrix

The method fast inverse using nested dissection (FIND) was proposed to calculate the diagonal entries of the inverse of a large sparse symmetric matrix. In this paper, we show how the FIND algorithm can be generalized to calculate off‐diagonal entries of the inverse that correspond to ‘short’ geometric distances within the computational mesh of the original matrix. The idea is to extend the downward pass in FIND that eliminates all nodes outside of each node cluster. In our advanced downwards pass, it eliminates all nodes outside of each ‘node cluster pair’ from a subset of all node cluster pairs. The complexity depends on how far (i,j) is from the main diagonal. In the extension of the algorithm, all entries of the inverse that correspond to vertex pairs that are geometrically closer than a predefined length limit l will be calculated. More precisely, let α be the total number of nodes in a two‐dimensional square mesh. We will show that our algorithm can compute O(α^{3 ∕ 2 + 2ε}) entries of the inverse in O(α^{3 ∕ 2 + 2ε}) time where l = O(α^{1 ∕ 4 + ε}) and 0 ≤ ε ≤1 ∕ 4. Numerical examples are given to illustrate the efficiency of the proposed method. Copyright © 2012 John Wiley & Sons, Ltd.     

On the approximate solution of some two‐dimensional singular integral equations

An approximation method for a wide class of two‐dimensional integral equations is proposed. The method is based on using a special function system. Orthonormality and good interaction with fundamental integral operators arising in partial differential equations are remarkable properties of this system. In addition, all the basis elements can easily be calculated by recurrence relations. Taking into account these properties we construct a numerical algorithm which does not require additional effort (such as quadrature) to compute the values of the fundamental operators on the basis elements. Copyright © 2001 John Wiley & Sons, Ltd.     

A decoupling two‐grid algorithm for the mixed Stokes‐Darcy model with the Beavers‐Joseph interface condition

In this article, a decoupling scheme based on two‐grid finite element for the mixed Stokes‐Darcy problem with the Beavers‐Joseph interface condition is proposed and investigated. With a restriction of a physical parameter α, we derive the numerical stability and error estimates for the scheme. Numerical experiments indicate that such two‐grid based decoupling finite element schemes are feasible and efficient. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1066–1082, 2014     

Non‐selfsimilar global solutions to a two‐dimensional system of conservation laws

This paper considers the two‐dimensional Riemann problem for a system of conservation laws that models the polymer flooding in an oil reservoir. The initial data are two different constant states separated by a smooth curve. By virtue of a nonlinear coordinate transformation, this problem is converted into another simple one. We then analyze rigorously the expressions of elementary waves. Based on these preparations, we obtain respectively four kinds of non‐selfsimilar global solutions and their corresponding criteria. It is shown that the intermediate state between two elementary waves is no longer a constant state and that the expression of the rarefaction wave is obtained by constructing an inverse function. These are distinctive features of the non‐selfsimilar global solutions. Copyright © 2017 John Wiley & Sons, Ltd.     

A note on the complex semi‐definite matrix Procrustes problem

This note outlines an algorithm for solving the complex ‘matrix Procrustes problem’. This is a least‐squares approximation over the cone of positive semi‐definite Hermitian matrices, which has a number of applications in the areas of Optimization, Signal Processing and Control. The work generalizes the method of Allwright (SIAM J. Control Optim. 1988; 26 (3):537–556), who obtained a numerical solution to the real‐valued version of the problem. It is shown that, subject to an appropriate rank assumption, the complex problem can be formulated in a real setting using a matrix‐dilation technique, for which the method of Allwright is applicable. However, this transformation results in an over‐parametrization of the problem and, therefore, convergence to the optimal solution is slow. Here, an alternative algorithm is developed for solving the complex problem, which exploits fully the special structure of the dilated matrix. The advantages of the modified algorithm are demonstrated via a numerical example. Copyright © 2007 John Wiley & Sons, Ltd.