Strang-Type Preconditioners for Solving Linear Systems from Delay Differential Equations

We consider the solution of delay differential equations (DDEs) by using boundary value methods (BVMs). These methods require the solution of one or more nonsymmetric, large and sparse linear systems. The GMRES method with the Strang-type block-circulant preconditioner is proposed for solving these linear systems. We show that if a P _{k 1},k ₂-stable BVM is used for solving an m-by-m system of DDEs, then our preconditioner is invertible and all the eigenvalues of the preconditioned system are clustered around 1. It follows that when the GMRES method is applied to solving the preconditioned systems, the method may converge fast. Numerical results are given to illustrate the effectiveness of our methods.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

The Fast Numerical Solution of Very Large Elliptic Difference Schemes

Let L_kv_k = g_k be a system of difference equations discretizingan elliptic boundary value problem. Assume the system to be"very large", that means that the number of unknowns exceedsthe capacity of storage. We present a method for solving theproblem with much less storage requirement. For two-dimensionalproblems the size of the needed storage decreases from O(h^–2)to (or even O(h^–5/4)). The computational work increasesonly by a factor about six. The technique can be generalizedto nonlinear problems. The algorithm is also useful for computerswith a small number of parallel processors.     

On the anticipation phenomenon for implicit linear discrete-time systems on finite intervals

Implicit linear discrete-time systems are systems describedby the difference equation Ex_k+1 = Fx_k + Gu_k. It is well knownthat, for such systems, the current value of a trajectory (x_k)may be dependent on future values of an input sequence (u_k).This property, which is called the anticipation phenomenon,has previously been studied by the authors for k running throughthe whole set of nonnegative integers. In this paper, we studythis phenomenon for systems defined on finite intervals. Inparticular, we give a quantitative characterization of anticipationphenomenon by introducing the so-called anticipation index ofa system.     

A Uniqueness Theorem in the Inverse Spectral Theory of a Certain Higher-Order Ordinary Differential Equation Using Paley-Wiener Methods

The paper examines a higher-order ordinary differential equationof the form where D = i(d/dx),and where the coefficients a_jk, j,k [0,m], with a_mm = 1, satisfycertain regularity conditions and are chosen so that the matrix(a_jk) is hermitean. It is also assumed that m > 1. More precisely,it is proved, using Paley–Wiener methods, that the correspondingspectral measure determines the equation up to conjugation bya function of modulus 1. The paper also discusses under whichadditional conditions the spectral measure uniquely determinesthe coefficients a_jk, j,k [0,m], j + k 2m, as well as b andthe boundary conditions at 0 and at b (if any).     

Stability in the Sense of Bounded Average Power

An R^m-valued sequence (x_k): = (x_k : k = 1, 2, ...), e.g. generatedrecursively by x_k = f_k (x_k–_k, U_k), is called ‘averagepth power bounded’ if (1/K) is bounded uniformly in K= 1, 2,.... (The case p = 2 may correspond to ‘power’in the physical sense.) This is a notion of stability. Givenestimates of the form: f_k (x, u) < a x + ¶ _k conditionsare obtained on the coefficient sequence (a_k) and the inputestimates e_k:=¶_k (u_k) which ensure this form of stabilityfor the output (x_k). In particular, a condition (utilized inan application to adaptive control) is obtained which imposes(i) a bound b on (a_k) and a ‘sparsity measure’ m(K) on #{kK: a_k>} as K ( >1) (ii) average pth power boundednesson (e_k), and (iii) a growth condition on (e_k) related to b andm (•). This condition is sharp.     

A new transform method for evolution partial differential equations

We introduce a new transform method for solving initial-boundary-valueproblems for linear evolution partial differential equationswith spatial derivatives of arbitrary order. This method isillustrated by solving several such problems on the half-line{t > 0, 0 < x < }, and on the quarter-plane {t >0, 0 < x_j < , j = 1, 2}. For equations in one space dimensionthis method constructs q(x, t) as an integral in the complexk-plane involving an x-transform of the initial condition anda t-transform of the boundary conditions. For equations in twospace dimensions it constructs q(x₁, x₂, t) as an integral inthe complex (k₁, k₂)-planes involving an (x₁, x₂)-transformof the initial condition, an (x₂, t)-transform of the boundaryconditions at x₁ = 0, and an (x₁, t)-transform of the boundaryconditions at x₂ = 0. This method is simple to implement andyet it yields integral representations which are particularlyconvenient for computing the long time asymptotics of the solution.     

Long-Time Behavior of Solutions of the Fast Diffusion Equations with Critical Absorption Terms

This paper is devoted to the long-time behavior of solutionsto the Cauchy problem of the porous medium equation u_t = (u^m)– u^p in Rⁿ x (0,) with (1 – 2/n)₊ < m < 1and the critical exponent p = m + 2/n. For the strictly positiveinitial data u(x,0) = O(1 + |x|)^–k with n + mn(2 –n + nm)/(2[2 – m + mn(1 – m)]) k < 2/(1 –m), we prove that the solution of the above Cauchy problem convergesto a fundamental solution of u_t = (u^m) with an additional logarithmicanomalous decay exponent in time as t .     

Fast iterative methods for symmetric sinc-Galerkin systems

The symmetric sinc-Galerkin method developed by Lund, when appliedto the second-order self-adjoint boundary value problem, givesrise to a symmetric coefficient matrix has a special structureso that it can be advantageously used in solving the discretesystem. In this paper, we employ the preconditioned conjugategradient method with banded matrices as preconditioners. Weprove that the condition number of the preconditioned matrixis uniformly bounded by a constant independent of the size ofthe matrix. In particular, we show that the solution of an n-by-ndiscrete symmetric sinc-Galerkin system can be obtained in O(nlog n) operations. We also extend our method to the self-adjointelliptic partial differential equation. Numerical results aregiven to illustrate the effectiveness of our fast iterativesolvers.     

BENFORD'S LAW FOR THE 3x + 1 FUNCTION

Benford's law (to base B) for an infinite sequence {x_k : k 1} of positive quantities x_k is the assertion that {log_B x_k: k 1} is uniformly distributed (mod 1). The 3x + 1 functionT(n) is given by T(n) = (3n + 1)/2 if n is odd, and T(n) = n/2if n is even. This paper studies the initial iterates x_k = T^(k)(x₀)for 1 k N of the 3x + 1 function, where N is fixed. It showsthat for most initial values x₀, such sequences approximatelysatisfy Benford's law, in the sense that the discrepancy ofthe finite sequence {log_B x_k : 1 k N} is small.     

On the Solution of Some Elliptic Difference Equations

Iterative methods for the solution of some nonlinear ellipticdifference systems, approximating the first boundary value problemare considered. If h > 0 is the network step in the spaceof variables x = (x₁, x₂,..., x_p) and 2m is the order of theoriginal boundary value problem, then the iterative methodsproposed give solution of accuracy with the expenditure ofO(|In | h^–(p+m–)) and O(|In | |In h| h^–p)arithmetic operations in the case of a general region and arectangular parallelepiped respectively. In the case p = 2 theestimate O(|In | h^{–[2+ (m/2)]}) is obtained if the regionis made up of rectangles with sides parallel to the co-ordinateaxes.     

On Waring's Problem in Number Fields

Let K be an algebraic number field of degree n over the rationals,and denote by J_k the subring of K generated by the kth powersof the integers of K. Then G_K(k) is defined to be the smallests1 such that, for all totally positive integers vJ_k of sufficientlylarge norm, the Diophantine equation (1.1) is soluble in totally non-negative integers _i of K satisfying N(_i)<<N(v)^1/k (1is). (1.2) In (1.2) and throughout this paper, all implicit constants areassumed to depend only on K, k, and s. The notation G_K(k) generalizesthe familiar symbol G(k) used in Waring's problem, since wehave G_Q(k) = G(k). By extending the Hardy–Littlewood circle method to numberfields, Siegel [8, 9] initiated a line of research (see [1–4,11]) which generalized existing methods for treating G(k). Thistypically led to upper bounds for G_K(k) of approximate strengthnB(k), where B(k) was the best contemporary upper bound forG(k). For example, Eda [2] gave an extension of Vinogradov'sproof (see [13] or [15]) that G(k)(2+o(1))k log k. The presentpaper will eliminate the need for lengthy generalizations assuch, by introducing a new and considerably shorter approachto the problem. Our main result is the following theorem.     

A HIGH-ORDER ACCURACY METHOD FOR SOLVING THE FRACTIONAL DIFFUSION EQUATIONS

In this paper, an efficient numerical method for solving the general fractional diffusion equations with Riesz fractional derivative is proposed by combining the fractional compact difference operator and the boundary value methods. In order to efficiently solve the generated linear large-scale system, the generalized minimal residual (GMRES) algorithm is applied. For accelerating the convergence rate of the iterative, the Strang-type, Chan-type and P-type preconditioners are introduced. The suggested method can reach higher order accuracy both in space and in time than the existing methods. When the used boundary value method is $A_{k1,k2}$-stable, it is proven that Strang-type preconditioner is invertible and the spectra of preconditioned matrix is clustered around 1. It implies that the iterative solution is convergent rapidly. Numerical experiments with the absorbing boundary condition and the generalized Dirichlet type further verify the efficiency.     

Determination of a Convex Body from Minkowski Sums of its Projections

For a convex body K in R^d and 1 K d – 1, let P_K (K)be the Minkowski sum (average) of all orthogonal projectionsof K onto k-dimensional subspaces of R^d. It is Known that theoperator P_k is injective if kd/2, k=3 for all d, and if k =2, d 14. It is shown that P_2k (K) determines a convex body K among allcentrally symmetric convex bodies and P_2k+1(K) determines aconvex body K among all bodies of constant width. Correspondingstability results are also given. Furthermore, it is shown thatany convex body K is determined by the two sets P_k (K) and P_k'(K) if 1 < k < k'. Concerning the range of P_k , 1 k d–2, it is shown that its closure (in the Hausdorff-metric)does not contain any polytopes other than singletons.     

Conversion of Polynomials between Different Polynomial Bases

The purpose of this paper is to derive a recursive scheme forthe evaluation of the coefficients in the expansion , in terms of the coefficients in the expansion , where both q_k(x) and Q_k(x) are polynomials in xof degree k, and where both q_k(x) and Q_k{x} satisfy recursionformulae of the type satisfied by orthogonal polynomials. Thesets {Q_k(x)} and {q_k(x)} need not be orthogonal polynomials,though they usually are in the applications. An applicationis made to the evaluation of integrals with oscillatory andsingular integrands.     

Moments of Some Stopping Rules

Let X_n for n1 be independent random variables with . Set . Define T_k,c,m=inf{nm:|k!S_k,n|>cn^k/2}.We study critical values c_k,p for k2 and p>0, such that for c<c_k,p and all m, and for c>c_k,p and all sufficientlylarge m. In particular, c_1,1=c_2,1=1, c_3,1=2 and c_4,1=3 undercertain moment conditions on X₁, when X_n are identically distributed.We also investigate perturbed stopping rules of the form T_h,m=inf{nm:h(S_1,n/n^1/2)<_nor >_n} for continuous functions h and random variables _naand _nb with a<b. Related stopping rules of the Wiener processare also considered via the Uhlenbeck process.     

On sinc discretization and banded preconditioning for linear third‐order ordinary differential equations

Some draining or coating fluid‐flow problems and problems concerning the flow of thin films of viscous fluid with a free surface can be described by third‐order ordinary differential equations (ODEs). In this paper, we solve the boundary value problems of such equations by sinc discretization and prove that the discrete solutions converge to the true solutions of the ODEs exponentially. The discrete solution is determined by a linear system with the coefficient matrix being a combination of Toeplitz and diagonal matrices. The system can be effectively solved by Krylov subspace iteration methods, such as GMRES, preconditioned by banded matrices. We demonstrate that the eigenvalues of the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the linear system. Numerical examples are given to illustrate the effective performance of our method. Copyright © 2010 John Wiley & Sons, Ltd.     

(2, 3, k)-generated groups of large rank

For any fixed k 3 7k \geq 7 there exist integers n_k and a_k such that if the ring R is generated by a set of m elements t₁,...,t_m, where 2t₁-t₁²2t_1-t_1^2 is a unit of finite multiplicative order, and n 3 n_k+ma_kn \geq n_k+ma_k, then the group E_n(R) generated by elementary transvections is an epimorphic image of the triangle group D(2,3,k).\Delta (2,3,k).     

Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials

Consider the (n + 1) ? (n + 1) Vandermonde-like matrix P=[p_i-1(_j-1)],where the polynomials p_o(x), ..., p_n(x) satisfy a three-termrecurrence relation. We develop algorithms for solving the primaland dual systems, Px = b and P^Ta = f respectively, in O(n²)arithmetic operations and O(n) elements of storage. These algorithmsgeneralize those of Bj?rck & Pereyra which apply to themonomial case p_i(x). When the p_i(x) are the Chebyshev polynomials,the algorithms are shown to be numerically unstable. However,it is found empirically that the addition of just one step ofiterative refinement is, in single precision, enough to makethe algorithms numerically stable.