Multiquadric quasi‐interpolation methods for solving partial differential algebraic equations

In this article, we propose two meshless collocation approaches for solving time dependent partial differential algebraic equations (PDAEs) in terms of the multiquadric quasi‐interpolation schemes. In presenting the process of the solution, the error is estimated. Furthermore, the comparisons on condition numbers of the collocation matrices using different methods and the sensitivity of the shape parameter c are given. With the use of the appropriate collocation points, the method for PDAEs with index‐2 is improved. The results show that the methods have some advantages over some known methods, such as the smaller condition numbers or more accurate solutions for PDAEs which has an modal index‐2 or an impulse solution with index‐2. Copyright © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 95–119, 2014     

A preconditioned low‐rank CG method for parameter‐dependent Lyapunov matrix equations

This paper is concerned with the numerical solution of symmetric large‐scale Lyapunov equations with low‐rank right‐hand sides and coefficient matrices depending on a parameter. Specifically, we consider the situation when the parameter dependence is sufficiently smooth, and the aim is to compute solutions for many different parameter samples. On the basis of existing results for Lyapunov equations and parameter‐dependent linear systems, we prove that the tensor containing all solution samples typically allows for an excellent low multilinear rank approximation. Stacking all sampled equations into one huge linear system, this fact can be exploited by combining the preconditioned CG method with low‐rank truncation. Our approach is flexible enough to allow for a variety of preconditioners based, for example, on the sign function iteration or the alternating direction implicit method. Copyright © 2013 John Wiley & Sons, Ltd.     

Spectral estimates for saddle point matrices arising in weak constraint four‐dimensional variational data assimilation

We consider the large sparse symmetric linear systems of equations that arise in the solution of weak constraint four‐dimensional variational data assimilation, a method of high interest for numerical weather prediction. These systems can be written as saddle point systems with a 3 × 3 block structure but block eliminations can be performed to reduce them to saddle point systems with a 2 × 2 block structure, or further to symmetric positive definite systems. In this article, we analyse how sensitive the spectra of these matrices are to the number of observations of the underlying dynamical system. We also obtain bounds on the eigenvalues of the matrices. Numerical experiments are used to confirm the theoretical analysis and bounds.     

Local preconditioners for two‐level non‐overlapping domain decomposition methods

We consider additive two‐level preconditioners, with a local and a global component, for the Schur complement system arising in non‐overlapping domain decomposition methods. We propose two new parallelizable local preconditioners. The first one is a computationally cheap but numerically relevant alternative to the classical block Jacobi preconditioner. The second one exploits all the information from the local Schur complement matrices and demonstrates an attractive numerical behaviour on heterogeneous and anisotropic problems. We also propose two implementations based on approximate Schur complement matrices that are cheaper alternatives to construct the given preconditioners but that preserve their good numerical behaviour. Through extensive computational experiments we study the numerical scalability and the robustness of the proposed preconditioners and compare their numerical performance with well‐known robust preconditioners such as BPS and the balancing Neumann–Neumann method. Finally, we describe a parallel implementation on distributed memory computers of some of the proposed techniques and report parallel performances. Copyright © 2001 John Wiley & Sons, Ltd.     

Split‐type octonion matrix

The split and hyperbolic (countercomplex) octonions are eight‐dimensional nonassociative algebras over the real numbers, which are in the form , where e_m's have different properties for them. The main purpose of this paper is to define the split‐type octonion and its matrix whose inputs are split‐type octonions and give some properties for them by using the real quaternions, split, and hyperbolic (countercomplex) octonions. On the other hand, to make some definitions, we present some operations on the split‐type octonions. Also, we show that every split‐type octonions can be represented by 2 × 2 real quaternion matrix and 4 × 4 complex number matrix. The information about the determinants of these matrix representations is also given. Besides, the main features of split‐type octonion matrix concept are given by using properties of  real quaternion matrices. Then, 8n × 8nreal matrix representations of split‐type octonion matrices are shown, and some algebraic structures are examined. Additionally, we introduce real quaternion adjoint matrices of split‐type octonion matrices. Moreover, necessary and sufficient conditions and definitions are given for split‐type octonion matrices to be special split‐type octonion matrices. We describe some special split‐type octonion matrices. Finally, oct‐determinant of split‐type octonion matrices is defined. Definitive and understandable examples of all definitions, theorems, and conclusions were given for a better understanding of all these concepts.     

Blended kernel approximation in the ℋ︁‐matrix techniques

Several types of ??‐matrices were shown to provide a data‐sparse approximation of non‐local (integral) operators in FEM and BEM applications. The general construction is applied to the operators with asymptotically smooth kernel function provided that the Galerkin ansatz space has a hierarchical structure. The new class of ??‐matrices is based on the so‐called blended FE and polynomial approximations of the kernel function and leads to matrix blocks with a tensor‐product of block‐Toeplitz (block‐circulant) and rank‐k matrices. This requires the translation (rotation) invariance of the kernel combined with the corresponding tensor‐product grids. The approach allows for the fast evaluation of volume/boundary integral operators with possibly non‐smooth kernels defined on canonical domains/manifolds in the FEM/BEM applications. (Here and in the following, we call domains canonical if they are obtained by translation or rotation of one of their parts, e.g. parallelepiped, cylinder, sphere, etc.) In particular, we provide the error and complexity analysis for blended expansions to the Helmholtz kernel. Copyright © 2002 John Wiley & Sons, Ltd.     

On order‐reducible sinc discretizations and block‐diagonal preconditioning methods for linear third‐order ordinary differential equations

By introducing a variable substitution, we transform the two‐point boundary value problem of a third‐order ordinary differential equation into a system of two second‐order ordinary differential equations (ODEs). We discretize this order‐reduced system of ODEs by both sinc‐collocation and sinc‐Galerkin methods, and average these two discretized linear systems to obtain the target system of linear equations. We prove that the discrete solution resulting from the linear system converges exponentially to the true solution of the order‐reduced system of ODEs. The coefficient matrix of the linear system is of block two‐by‐two structure, and each of its blocks is a combination of Toeplitz and diagonal matrices. Because of its algebraic properties and matrix structures, the linear system can be effectively solved by Krylov subspace iteration methods such as GMRES preconditioned by block‐diagonal matrices. We demonstrate that the eigenvalues of certain approximation to the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the discretized linear system, and we use numerical examples to illustrate the feasibility and effectiveness of this new approach. Copyright © 2013 John Wiley & Sons, Ltd.     

Preconditioners for non‐Hermitian Toeplitz systems

In this paper, we construct new ω‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)‐Toeplitz matrices with spectral condition number 𝒪(N^α) the corresponding PCG method requires at most 𝒪(N log² N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd.     

A general approach to analyse preconditioners for two‐by‐two block matrices

Two‐by‐two block matrices arise in various applications, such as in domain decomposition methods or when solving boundary value problems discretised by finite elements from the separation of the node set of the mesh into ‘fine’ and ‘coarse’ nodes. Matrices with such a structure, in saddle point form arise also in mixed variable finite element methods and in constrained optimisation problems. A general algebraic approach to construct, analyse and control the accuracy of preconditioners for matrices in two‐by‐two block form is presented. This includes both symmetric and nonsymmetric matrices, as well as indefinite matrices. The action of the preconditioners can involve element‐by‐element approximations and/or geometric or algebraic multigrid/multilevel methods. Copyright © 2011 John Wiley & Sons, Ltd.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

ℋ︁‐matrices for the convection‐diffusion equation

Hierarchical matrices (ℋ︁‐matrices) provide a technique for the sparse approximation of large, fully populated matrices. This technique has been shown to be applicable to stiffness matrices arising in boundary element method applications where the kernel function displays certain smoothness properties. The error estimates for an approximation of the kernel function by a separable function can be carried over directly to error estimates for an approximation of the stiffness matrix by an ℋ︁‐matrix, using a certain standard partitioning and admissibility condition for matrix blocks. Similarly, ℋ︁‐matrix techniques can be applied in the finite element context where it is the inverse of the stiffness matrix that is fully populated. Here one needs a separable approximation of Green's function of the underlying boundary value problem in order to prove approximability by matrix blocks of low rank. Unfortunately, Green's function for the convection‐diffusion equation does not satisfy the required smoothness properties, hence prohibiting a straightforward generalization of the separable approximation through Taylor polynomials. We will use Green's function to motivate a modification in the (hierarchical) partitioning of the index set and as a consequence the resulting hierarchy of block partitionings as well as the admissibility condition. We will illustrate the effect of the proposed modifications by numerical results.     

A new stabilized finite element method for advection‐diffusion‐reaction equations

In this article, a new stabilized finite element method is proposed and analyzed for advection‐diffusion‐reaction equations. The key feature is that both the mesh‐dependent Péclet number and the mesh‐dependent Damköhler number are reasonably incorporated into the newly designed stabilization parameter. The error estimates are established, where, up to the regularity‐norm of the exact solution, the explicit‐dependence of the diffusivity, advection, reaction, and mesh size (or the dependence of the mesh‐dependent Péclet number and the mesh‐dependent Damköhler number) is revealed. Such dependence in the error bounds provides a mathematical justification on the effectiveness of the proposed method for any values of diffusivity, advection, dissipative reaction, and mesh size. Numerical results are presented to illustrate the performance of the method. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 616–645, 2016     

Order optimal preconditioners for fully implicit Runge‐Kutta schemes applied to the bidomain equations

The partial differential equation part of the bidomain equations is discretized in time with fully implicit Runge–Kutta methods, and the resulting block systems are preconditioned with a block diagonal preconditioner. By studying the time‐stepping operator in the proper Sobolev spaces, we show that the preconditioned systems have bounded condition numbers given that the Runge–Kutta scheme is A‐stable and irreducible with an invertible coefficient matrix. A new proof of order optimality of the preconditioners for the one‐leg discretization in time of the bidomain equations is also presented. The theoretical results are verified by numerical experiments. Additionally, the concept of weakly positive‐definite matrices is introduced and analyzed. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq Eq 27: 1290–1312, 2011     

Identification problem for a one‐dimensional vibrating system

We discuss an inverse problem of determining a coefficient matrix and an initial value for a one‐dimensional non‐symmetric hyperbolic system of the first order by means of boundary values over a time interval. Provided that a time interval is sufficiently long and a given initial value satisfies some non‐degeneracy condition, we characterize coefficient matrices and initial values realizing the same boundary values. In the case where the initial value is fixed, we can prove the uniqueness in determining all the components of the coefficient matrices. The proof is based on a transformation formula and spectral properties. Copyright © 2005 John Wiley & Sons, Ltd.     

A state‐dependent Markov‐modulated mechanism for generating events and stochastic models

In this paper, we introduce a versatile block‐structured state‐dependent event (BSDE) approach that provides a methodological tool to construct non‐homogeneous Markov‐modulated stochastic models. Alternatively, the BSDE approach can be used to construct even a part (e.g. the arrival process) of the model. To illustrate the usefulness of the BSDE approach, several arrival patterns as well as queueing and epidemic models are considered. In particular, we deal with a state‐dependent quasi‐birth‐and‐death process that gives a constructive generalization of the scalar birth‐and‐death process and the homogeneous quasi‐birth‐and‐death process. Copyright © 2009 John Wiley & Sons, Ltd.     

Finite‐time flocking problem of a Cucker–smale‐type self‐propelled particle model

In this article, we propose a Cucker–Smale‐type self‐propelled particle model with continuous non‐Lipschitz protocol. We show that the flocking can occur in finite time if the communication rate function satisfies a lower bound condition. Both our theoretical and numerical results uncover a power‐law relationship between the convergence time and the number of individuals. Our result implies that the individuals in groups with high density can transit rapidly to ordered collective motion. We also investigate the influence of control parameter on the convergence speed. © 2015 Wiley Periodicals, Inc. Complexity 21: 354–361, 2016     

Non‐homogeneous Navier–Stokes systems with order‐parameter‐dependent stresses

We consider the Navier–Stokes system with variable density and variable viscosity coupled to a transport equation for an order‐parameter c. Moreover, an extra stress depending on c and ?c, which describes surface tension like effects, is included in the Navier–Stokes system. Such a system arises, e.g. for certain models of granular flows and as a diffuse interface model for a two‐phase flow of viscous incompressible fluids. The so‐called density‐dependent Navier–Stokes system is also a special case of our system. We prove short‐time existence of strong solution in L^q‐Sobolev spaces with q>d. We consider the case of a bounded domain and an asymptotically flat layer with a combination of a Dirichlet boundary condition and a free surface boundary condition. The result is based on a maximal regularity result for the linearized system. Copyright © 2010 John Wiley & Sons, Ltd.     

Block‐triangular preconditioners for PDE‐constrained optimization

In this paper we investigate the possibility of using a block‐triangular preconditioner for saddle point problems arising in PDE‐constrained optimization. In particular, we focus on a conjugate gradient‐type method introduced by Bramble and Pasciak that uses self‐adjointness of the preconditioned system in a non‐standard inner product. We show when the Chebyshev semi‐iteration is used as a preconditioner for the relevant matrix blocks involving the finite element mass matrix that the main drawback of the Bramble–Pasciak method—the appropriate scaling of the preconditioners—is easily overcome. We present an eigenvalue analysis for the block‐triangular preconditioners that gives convergence bounds in the non‐standard inner product and illustrates their competitiveness on a number of computed examples. Copyright © 2010 John Wiley & Sons, Ltd.     

Stability and convergence of the mark and cell finite difference scheme for Darcy‐Stokes‐Brinkman equations on non‐uniform grids

In this paper, we consider the mark and cell (MAC) method for Darcy‐Stokes‐Brinkman equations and analyze the stability and convergence of the method on nonuniform grids. Firstly, to obtain the stability for both velocity and pressure, we establish the discrete inf‐sup condition. Then we introduce an auxiliary function depending on the velocity and discretizing parameters to analyze the super‐convergence. Finally, we obtain the second‐order convergence in L2 norm for both velocity and pressure for the MAC scheme, when the perturbation parameter ? is not approaching 0. We also obtain the second‐order convergence for some terms of ∥·∥_? norm of the velocity, and the other terms of ∥·∥_? norm are second‐order convergence on uniform grid. Numerical experiments are carried out to verify the theoretical results.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.