Convergence of multistep discretizations of DAEs

Standard ODE methods such as linear multistep methods encounter difficulties when applied to differential-algebraic equations (DAEs) of index greater than 1. In particular, previous results for index 2 DAEs have practically ruled out the use of all explicit methods and of implicit multistep methods other than backward difference formulas (BDFs) because of stability considerations. In this paper we embed known results for semi-explicit index 1 and 2 DAEs in a more comprehensive theory based on compound multistep and one-leg discretizations. This explains and characterizes the necessary requirements that a method must fulfill in order to be applicable to semi-explicit DAEs. Thus we conclude that the most useful discretizations are those that avoid discretization of the constraint. A freer use of e.g. explicit methods for the non-stiff differential part of the DAE is then possible.Dedicated to Germund Dahlquist on the occasion of his 70th birthdayThis author thanks the Centro de Estadística y Software Matemático de la Universidad Simón Bolivar (CESMa) for permitting her free use of its research facilities.Partial support by the Swedish Research Council for Engineering Sciences TFR under contract no. 222/91-405.     

A search strategy for the elementary cycles of a directed graph

The most successful known algorithms enumerating the elementary cycles of a directed graph are based on a backtracking strategy. Such existing algorithms are discussed and a new backtracking algorithm is proposed which is bounded byO(N +M(C + 1)) time, for a directed graph withN vertices,M edges andC elementary cycles.Research supported by the Conselho National de Desenvolvimento Científico e Tecnológico — CNPq — Brasil.     

Shrinkage of de Morgan formulae under restriction

It is shown that a random restriction leaving only a fraction ? of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O(E^(5?√2)/2) = O(?^1.63). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long-standing result of O(?^1.5) by Subbotovskaya and a recent improvement to O(?^(21?√73)/8) = O(?^1.55) by Nisan and Impagliazzo. The New exponent yields an increased lower bound of n^{(7?√3)/2?o(1)} = Ω(n^2.63) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP. © 1993 John Wiley & Sons, Inc.     

Bounds for algebraic gossip on graphs

We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading: Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(Δn) where Δ is the maximum degree of the graph. This leads to a tight bound of for bounded degree graphs and an upper bound of O(n²) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of . Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 185–217, 2014     

Reversible methods of Runge-Kutta type for Index-2 DAEs

Summary. A new interpretation of Runge-Kutta methods for differential algebraic equations (DAEs) of index 2 is presented, where a step of the method is described in terms of a smooth map (smooth also with respect to the stepsize). This leads to a better understanding of the convergence behavior of Runge-Kutta methods that are not stiffly accurate. In particular, our new framework allows for the unified study of two order-improving techniques for symmetric Runge-Kutta methods (namely post-projection and symmetric projection) specially suited for solving reversible index-2 DAEs.Mathematics Subject Classification (1991): 65L05, 65L06     

Reduction Algorithm for the NPMLE for the Distribution Function of Bivariate Interval-Censored Data

This article considers computational aspects of the nonparametric maximum likelihood estimator (NPMLE) for the distribution function of bivariate interval-censored data. The computation of the NPMLE consists of a parameter reduction step and an optimization step. This article focuses on the reduction step and introduces two new reduction algorithms: the Tree algorithm and the HeightMap algorithm. The Tree algorithm is mentioned only briefly. The HeightMap algorithm is discussed in detail and also given in pseudo code. It is a fast and simple algorithm of time complexityO(n²). This is an order faster than the best known algorithm thus far by Bogaerts and Lesaffre. We compare the new algorithms to earlier algorithms in a simulation study, and demonstrate that the new algorithms are significantly faster. Finally, we discuss how the HeightMap algorithm can be generalized to d-dimensional data with d > 2. Such a multivariate version of the HeightMap algorithm has time complexity O(n^d).     

Bounds on the real stability radius for affinely perturbed differential‐algebraic systems

Analysis of robust stability for a family (E( Δ ), A( Δ )) of linear differential‐algebraic equations (DAEs) depending on perturbations Δ ∈ Δ of some parameters is more difficult than for the classical ODE‐case where E(·) can be identified with I_n ∈ ℝ^n×n. We start with an electric circuit example for motivation. Then, after defining the class of parameterized DAEs we are dealing with we consider two kinds of stability radii: One concerns preservation of the structure for the perturbed system (including the algebraic index and dimension of the subspace belonging to the finite spectrum of (E(·), A(·))). The second cares for stability of the finite spectrum as known from the classical case. Both can be treated independently and their combination yields the stability radius of the family. From this, it is possible to derive characterizations of both stability radii which are based on the structured singular value (SSV). However, the upper bounds may be very conservative in the real perturbation case – thus we introduce a variational principle which also characterizes the stability radius and allows for the computation of better upper bounds in the real perturbation case. In combination with the SSV‐based method this yields quite small intervals for the stability radius to lie in. Finally, some numerical results for the electric circuit example are presented.     

A collocation method for differential equations with one‐point Taylor initial conditions

This paper presents a new multistep collocation method for nth order differential equations. The interval of interest is first divided into N subintervals. By determining interval conditions in Taylor interpolation in each subinterval, Taylor polynomials are calculated with different step lengths. Then the obtained solutions in each subinterval are used as initial conditions in the next step. Optimal error is assessed using Peano lemma, which shows that the errors decay by decreasing the step length. In particular, for fixed step length h, the error is of O(m^?m), where m is the number of collocation points in each subinterval. Meanwhile, for fixed m, the error is of O(h^m). Numerical examples demonstrate the validity and high accuracy of the proposed method even for stiff problems.     

On an interval-arithmetic matrix method

Hansen and Smith have proposed a method for solving linear algebraic systems with interval coefficients which produces good results if the intervals are narrow. In this paper we show that the error of their method isO(W ²), whereW is the width of the set of coefficients. The effects of round-off errors are not considered.Supported in part by NSF grant GJ-797.     

Variational splines for the numerical solution of singular differential equations

The numerical parametrization method (PM), originally created for optimal control problems, is specificated for classical calculus of variation problems that arise in connection with singular implicit (IDEs) and differential-algebraic equations (DAEs). The PM for IDEs is based on representation of the required solution as a spline with moving knots and on minimization of the discrepancy functional with respect to the spline parameters. Such splines are named variational splines. For DAEs only finite entering functions can be represented by splines, and the functional under minimization is the discrepancy of the algebraic subsystem. The first and the second derivatives of the functionals are calculated in two ways – for DAEs with the help of adjoint variables, and for IDE directly. The PM does not use the notion of differentiation index, and it is applicable to any singular equation having a solution. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

One-step 9-stage Hermite–Birkhoff–Taylor DAE solver of order 10

The HBT(10)9 method for ODEs is expanded into HBT(10)9DAE for solving nonstiff and moderately stiff systems of fully implicit differential algebraic equations (DAEs) of arbitrarily high fixed index. A scheme to generate first-order derivatives at off-step points is combined with Pryce scheme which generates high order derivatives at step points. The stepsize is controlled by a local error estimator. HBT(10)9DAE uses only the first four derivatives of y instead of the first 10 required by Taylor’s series method T10DAE of order 10. Dormand–Prince’s DP(8,7)13M for ODEs is extended to DP(8,7)DAE for DAEs. HBT(10)9DAE wins over DP(8,7)DAE on several test problems on the basis of CPU time as a function of relative error at the end of the interval of integration. An index-5 problem is equally well solved by HBT(10)9DAE and T10DAE. On this problem, the error in the solution by DP(8,7)DAE increases as time increases.     

Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT: Experimental Evaluation

For problems SAT and MAX SAT, local search algorithms are widely acknowledged as one of the most effective approaches. Most of the local search algorithms are based on the 1-flip neighborhood, which is the set of solutions obtainable by flipping the truth assignment of one variable. In this paper, we consider r-flip neighborhoods for r = 2, 3, and examine their effectiveness by computational experiments. In the accompanying paper, we proposed new implementations of these neighborhoods, and showed that the expected size of 2-flip neighborhood is O(n + m) and that of 3-flip neighborhood is O(m + t ² n), compared to their original size O(n ²) andO(n ³), respectively, where n is the number of variables, m is the number of clauses and t is the maximum number of appearances of one variable. These are used in this paper under the framework of tabu search and other metaheuristic methods, and compared with other existing algorithms with 1-flip neighborhood. The results exhibit good prospects of larger neighborhoods.     

Phase‐fitted,six‐step methods for solving x′′ = f(t,x)

An explicit, six‐step method of sixth order is presented and tuned for the numerical solution of x′′ = f(t,x). This method is explicit, hybrid, and uses two function evaluations (stages) per step. Its coefficients are varied and depend on the step size. This variance comes from the demand of the method to nullify the phase errors produced when solving the standard simple oscillator. The first and second derivative of this error vanish also. Numerical tests in a set of relevant problems illustrate the efficiency of the newly derived method.     

Extrapolation algorithms for solving nonlinear boundary integral equations by mechanical quadrature methods

We study the numerical solution procedure for two-dimensional Laplace’s equation subjecting to non-linear boundary conditions. Based on the potential theory, the problem can be converted into a nonlinear boundary integral equations. Mechanical quadrature methods are presented for solving the equations, which possess high accuracy order O(h ³) and low computing complexities. Moreover, the algorithms of the mechanical quadrature methods are simple without any integration computation. Harnessing the asymptotical compact theory and Stepleman theorem, an asymptotic expansion of the errors with odd powers is shown. Based on the asymptotic expansion, the h ³ −Richardson extrapolation algorithms are used and the accuracy order is improved to O(h ⁵). The efficiency of the algorithms is illustrated by numerical examples.     

Runge-Kutta schemes that maintain invariant solutions for differential algebraic systems

Implicit Runge-Kutta (IRK) methods and projected IRK methods for the solution of semiexplicit index-2 systems of differential algebraic systems (DAEs) have been proposed by several authors. In this paper we prove that if a method satisfiesBA+A ^t B–bb ^t =0, it conserves quadratic invariants of DAEs.     

Numerical solution to a one‐dimensional thermoplastic problem with unilateral constraint

In this article, we present a numerical simulation of one‐dimensional problem of quasi‐static contact with an elastic obstacle. A finite difference scheme is derived by the method of reduction of order on uniform meshes. The stability and convergence are proved. The convergence order is of O(τ² + h²), where τ and h are the time step size and the space step size, respectively. Some numerical examples demonstrate the theoretical results. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

Higher order representations of the Robbins–Monro process

For quasi-linear regression functions, the Robbins–Monro process X_n is decomposed in a sum of a linear form and a quadratic form both defined in the observation errors. Under regularity conditions, the remainder term is of order O(n^−3/2) with respect to the L_p-norm. If a cubic form is added, the remainder term can be improved up to an order of O(n⁻²). As a corollary the expectation of X_n is expanded up to an error of order O(n⁻²). This is used to correct the bias of X_n up to an error of order O(n^−3/2 log n).     

A priori error estimates of an extrapolated space‐time discontinuous galerkin method for nonlinear convection‐diffusion problems

We deal with the numerical solution of a scalar nonstationary nonlinear convection‐diffusion equation. We employ a combination of the discontinuous Galerkin finite element (DGFE) method for the space as well as time discretization. The linear diffusive and penalty terms are treated implicitly whereas the nonlinear convective term is treated by a special higher order explicit extrapolation from the previous time step, which leads to the necessity to solve only a linear algebraic problem at each time step. We analyse this scheme and derive a priori asymptotic error estimates in the L^∞(L²) –norm and the L²(H¹) –seminorm with respect to the mesh size h and time step τ. Finally, we present an efficient solution strategy and numerical examples verifying the theoretical results. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1456–1482, 2010     

Solving the equation −uxx − ϵuyy = f(x,y, u) by an O(h4) finite difference method

The semi‐linear equation −u_xx − ϵu_yy = f(x, y, u) with Dirichlet boundary conditions is solved by an O(h⁴) finite difference method, which has local truncation error O(h²) at the mesh points neighboring the boundary and O(h⁴) at most interior mesh points. It is proved that the finite difference method is O(h⁴) uniformly convergent as h → 0. The method is considered in the form of a system of algebraic equations with a nine diagonal sparse matrix. The system of algebraic equations is solved by an implicit iterative method combined with Gauss elimination. A Mathematica module is designed for the purpose of testing and using the method. To illustrate the method, the equation of twisting a springy rod is solved. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 395–407, 2000     

Optimized look-ahead recurrences for adjacent rows in the Padé table

A new look-ahead algorithm for recursively computing Padé approximants is introduced. It generates a subsequence of the Padé approximants on two adjacent rows (defined by fixed numerator degree) of the Padé table. Its two basic versions reduce to the classical Levinson and Schur algorithms if no look-ahead is required. The new algorithm can be viewed as a combination of the look-ahead sawtooth and the look-ahead Levinson and Schur algorithms that we proposed before, but now the look-ahead step size is minimal (as in the sawtooth version) and the computational costs are as low as in the least expensive competing algorithms (including our look-ahead Levinson and Schur algorithms). The underlying recurrences link well-conditioned basic pairs,i.e., pairs of sufficiently different neighboring Padé forms.The algorithm can be used to solve Toeplitz systems of equationsTx = b. In this application it comes in several versions: anO(N ²) Levinson-type form, anO(N ²) Schur-type form, and a superfastO(N log² N) Schur-type version. As an option of the first two versions, the corresponding block LDU decompositions ofT ^–1 orT, respectively, can be found.