Generalized Padé approximations to the exponential function

The stability properties of the Padé rational approximations to the exponential function are of importance in determining the linear stability properties of several classes of Runge-Kutta methods. It is well known that the Padé approximationR _n,m (z) =N _n,m (z)/M _n,m (z), whereN _n,m (z) is of degreen andM _n,m (z) is of degreem, is A-stable if and only if 0 m – n 2, a result first conjectured by Ehle. In the study of the linear stability properties of the broader class of general linear methods one must generalize these rational approximations. In this paper we introduce a generalization of the Padé approximations to the exponential function and present a method of constructing these approximations for arbitrary order and degree. A generalization of the Ehle inequality is considered and, in the case of the quadratic Padé approximations, evidence is presented that suggests the inequality is both necessary and sufficient for A-stability. However, in the case of the cubic Padé approximations, the inequality is shown to be insufficient for A-stability. A generalization of the restricted Padé approximation, in which the denominator has a singlem-fold zero, is also introduced. A procedure for the construction of these restricted approximations is described, and results are presented on the A-stability of the restricted quadratic Padé approximations. Finally, to demonstrate the connection between a generalized Padé approximation and a general linear method, a specific general linear method is constructed with a stability region corresponding to a given quadratic Padé approximation.     

Performance analysis of AAL multiplexer with CBR traffic and bursty traffic

This paper models and evaluates the AAL multiplexer to analyze AAL protocol in ATM networks. We consider an AAL multiplexer in which a single periodically deterministic CBR traffic stream and several variable size bursty background traffic streams are multiplexed and one ATM cell stream goes out. We model the AAL multiplexer as aB ^X +D/D/1/K queue and analyze this queueing system. We represent various performance measures such as loss probability and waiting time in the basis of cell and packet.     

Method of Generalized Moment Representations in the Theory of Rational Approximation (A Survey)

We give a survey of the method of generalized moment representations introduced by Dzyadyk in 1981 and its applications to Padé approximations. In particular, some properties of biorthogonal polynomials are investigated and numerous important examples are given. We also consider applications of this method to joint Padé approximations, Padé–Chebyshev approximations, Hermite–Padé approximations, and two-point Padé approximations.     

Transient distributions of level dependent quasi-birth-death processes with linear transition rates

Many queueing systems such asM/M/s/K retrial queue with impatient customers, MAP/PH/1 retrial queue, retrial queue with two types of customers andMAP/M/∞ queue can be modeled by a level dependent quasi-birth-death (LDQBD) process with linear transition rates of the form λ_k = α+ βk at each levelk. The purpose of this paper is to propose an algorithm to find transient distributions for LDQBD processes with linear transition rates based on the adaptive uniformizaton technique introduced by van Moorsel and Sanders [11]. We apply the algorithm to some retrial queues and present numerical results.     

Computing the Matrix Cosine

An algorithm is developed for computing the matrix cosine, building on a proposal of Serbin and Blalock. The algorithm scales the matrix by a power of 2 to make the -norm less than or equal to 1, evaluates a Padé approximant, and then uses the double angle formula cos(2A)=2cos(A)²–I to recover the cosine of the original matrix. In addition, argument reduction and balancing is used initially to decrease the norm. We give truncation and rounding error analyses to show that an [8,8] Padé approximant produces the cosine of the scaled matrix correct to machine accuracy in IEEE double precision arithmetic, and we show that this Padé approximant can be more efficiently evaluated than a corresponding Taylor series approximation. We also provide error analysis to bound the propagation of errors in the double angle recurrence. Numerical experiments show that our algorithm is competitive in accuracy with the Schur–Parlett method of Davies and Higham, which is designed for general matrix functions, and it is substantially less expensive than that method for matrices of -norm of order 1. The dominant computational kernels in the algorithm are matrix multiplication and solution of a linear system with multiple right-hand sides, so the algorithm is well suited to modern computer architectures.     

A note on Radau and Lobatto formulae for O.D.E.: s

There exist Runge-Kutta methods based on Radau and Lobatto quadrature formulae. One class gives the set of all first and second above diagonal Padé approximations and another class gives the set of all first and second subdiagonal Padé approximations to the exponential function. A new short proof of the strongA-stability of the latter class of methods and a connection between these two classes are presented.     

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.     

Massively time-parallel,approximate simulation of loss queueing systems

A time-parallel simulation obtains parallelism by partitioning the time domain of the simulation. An approximate time-parallel simulation algorithm named GG1K is developed for acyclic networks of loss FCFSG/G/1/K queues. The GG1K algorithm requires two phases. In the first phase, a similar system (i.e. aG/G/1/ queue) is simulated using the GLM algorithm. Then the resultant trajectory is transformed into an approximateG/G/1/K trajectory in the second phase. The closeness of the approximation is investigated theoretically and experimentally. Our results show that the approximation is highly accurate except whenK is very small (e.g. 5) in certain models. The algorithm exploits unbounded parallelism and can achieve near-linear speedup when the number of arrivals simulated is sufficiently large.     

A superfast algorithm for multi-dimensional Padé systems

For a vector ofk+1 matrix power series, a superfast algorithm is given for the computation of multi-dimensional Padé systems. The algorithm provides a method for obtaining matrix Padé, matrix Hermite Padé and matrix simultaneous Padé approximants. When the matrix power series is normal or perfect, the algorithm is shown to calculate multi-dimensional matrix Padé systems of type (n ₀,...,n _k ) inO(n · log²n) block-matrix operations, where n=n ₀+...+n _k . Whenk=1 and the power series is scalar, this is the same complexity as that of other superfast algorithms for computing Padé systems. Whenk>1, the fastest methods presently compute these matrix Padé approximants with a complexity ofO(n²). The algorithm succeeds also in the non-normal and non-perfect case, but with a possibility of an increase in the cost complexity.Supported in part by NSERC grant No. A8035.Partially supported by NSERC operating grant No. 6194.     

A universal building block for the approximate analysis of a shared buffer ATM switch architecture

A universal analytic approximation is proposed for the performance analysis of a general queueing model of a shared buffer ATM switch architecture with bursty arrivals. The forms of the joint, aggregate and marginal state probabilities are characterised via entropy maximisation. As an application, a continuous-time maximum entropy (ME) solution is implemented at equilibrium by assuming that the arrival process to each port of the ATM switch is modelled by a Compound Poisson Process (CPP) with geometrically distributed batches. Consequently, efficientz-transform-type recursive expressions of low computational cost are derived. Validation tests against simulation show that the ME approximation is credible with a very good error-level. Moreover, performance bounds for the mean queue length and cell-loss probability at each output port are experimentally defined over those generated by Interrupted Poisson Processes (IPPs) having the same first two interarrival-time moments.This work is sponsored by the Science and Engineering Research Council (SERC), UK, under grants GR/F 29271 and GR/H 18609.     

Analysis of a tandem network model of a single-router Network-on-Chip

We study a single-router Network-on-Chip modelled as a tandem queueing network. The first node is a geo ^K /D/1 queue (K fixed) representing a network interface, and the second node is a ./G/1 queue representing the packet switch. If K>1 we have train arrivals at the second node. If K=1 the arrival process of the second node reduces to a Bernoulli process. In the latter case, routers have been studied extensively as part of ATM and LAN networks under the assumption that the number of input ports N tends to infinity. In Networks-on-Chips N is usually 4 or 5 and results for ATM and LAN routers lead to inaccurate results. We introduce a new approximation scheme that yields accurate results for small switches. In addition to this we analyse the tandem network, both for K=1 and K>1, and we approximate the mean sojourn time in the switch and the mean end-to-end delay. If N=4 our approximation has a relative error of only 4.5% if K=6 and 1% if K=1.     

A Tandem Queue with Blocking and Markovian Arrival Process

Queueing networks with blocking have proved useful in modelling of data communications and production lines. We study such a network consisting of a sequence of two service stations with an infinite queue allowed before the first station and no intermediate queue allowed between them. This restriction results in the blocking of the first station whenever a unit having completed its service in that station cannot enter into the second one due to the presence of another unit there. The input of units to the network is the MAP (Markovian Arrival Process). At the first station, service requirements are of phase type whereas service times at the second station are arbitrarily distributed. The focus is on the embedded process at departures. The essential tool in our analysis is the general theory on Markov renewal processes of M/G/1-type.     

Analyticity of single-server queues in light traffic

Recently, several methods have been proposed to approximate performance measures of queueing systems based on their light traffic derivatives, e.g., the MacLaurin expansion, the Padé approximation, and interpolation with heavy traffic limits. The key condition required in all these approximations is that the performance measures be analytic when the arrival rates equal to zero. In this paper, we study theGI/G/1 queue. We show that if the c.d.f. of the interarrival time can be expressed as a MacLaurin series over [0, ), then the mean steady-state system time of a job is indeed analytic when the arrival rate to the queue equals to zero. This condition is satisfied by phase-type distributions but not c.d.f.'s without support [0, ), such as uniform and shifted exponential distributions. In fact, we show through two examples that the analyticity does not hold for most commonly used distribution functions which do not satisfy this condition.     

Asymptotics in the MAP/G/1 Queue with Critical Load

When the offered load ρ is 1, we investigate the asymptotic behavior of the stationary measure for the MAP/G/1 queue and the asymptotic behavior of the loss probability for the finite buffer MAP/G/1/K + 1 queue. Unlike Baiocchi [Stochastic Models 10(1994):867–893], we assume neither the time reversibility of the MAP nor the exponential moment condition for the service time distribution. Our result generalizes the result of Baiocchi for the critical case ρ = 1 and solves the problem conjectured by Kim et al. [Operations Research Letters 36(2008):127–132].     

A type of matrix Padé approximant inspired by scalar component models

In this paper we define a type of matrix Padé approximant inspired by the identification stage of multivariate time series models considering scalar component models. Of course, the formalization of certain properties in the matrix Padé approximation framework can be applied to time series models and in other fields. Specifically, we want to study matrix Padé approximants as follows: to find rational representations (or rational approximations) of a matrix formal power series, with both matrix polynomials, numerator and denominator, satisfying three conditions: (a) minimum row degrees for the numerator and denominator, (b) an invertible denominator at the origin, and (c) canonical representation (without free parameters).     

Smoothing schemes for reaction-diffusion systems with nonsmooth data

Cox and Matthews [S.M. Cox, P.C. Matthews, Exponential time differencing for stiff systems, J. Comput. Phys. 176 (2002) 430–455] developed a class of Exponential Time Differencing Runge–Kutta schemes (ETDRK) for nonlinear parabolic equations; Kassam and Trefethen [A.K. Kassam, Ll. N. Trefethen, Fourth-order time stepping for stiff pdes, SIAM J. Sci. Comput. 26 (2005) 1214–1233] have shown that these schemes can suffer from numerical instability and they proposed a modified form of the fourth-order (ETDRK4) scheme. They use complex contour integration to implement these schemes in a way that avoids inaccuracies when inverting matrix polynomials, but this approach creates new difficulties in choosing and evaluating the contour for larger problems. Neither treatment addresses problems with nonsmooth data, where spurious oscillations can swamp the numerical approximations if one does not treat the problem carefully. Such problems with irregular initial data or mismatched initial and boundary conditions are important in various applications, including computational chemistry and financial engineering. We introduce a new version of the fourth-order Cox–Matthews, Kassam–Trefethen ETDRK4 scheme designed to eliminate the remaining computational difficulties. This new scheme utilizes an exponential time differencing Runge–Kutta ETDRK scheme using a diagonal Padé approximation of matrix exponential functions, while to deal with the problem of nonsmooth data we use several steps of an ETDRK scheme using a sub-diagonal Padé formula. The new algorithm improves computational efficiency with respect to evaluation of the high degree polynomial functions of matrices, having an advantage of splitting the matrix polynomial inversion problem into a sum of linear problems that can be solved in parallel. In this approach it is only required that several backward Euler linear problems be solved, in serial or parallel. Numerical experiments are described to support the new scheme.     

A matrix-analytic solution for the DBMAP/PH/1 priority queue

Priority queueing models have been commonly used in telecommunication systems. The development of analytically tractable models to determine their performance is vitally important. The discrete time batch Markovian arrival process (DBMAP) has been widely used to model the source behavior of data traffic, while phase-type (PH) distribution has been extensively applied to model the service time. This paper focuses on the computation of the DBMAP/PH/1 queueing system with priorities, in which the arrival process is considered to be a DBMAP with two priority levels and the service time obeys a discrete PH distribution. Such a queueing model has potential in performance evaluation of computer networks such as video transmission over wireless networks and priority scheduling in ATM or TDMA networks. Based on matrix-analytic methods, we develop computation algorithms for obtaining the stationary distribution of the system numbers and further deriving the key performance indices of the DBMAP/PH/1 priority queue. AMS subject classifications: 60K25 · 90B22 · 68M20 The work was supported in part by grants from RGC under the contracts HKUST6104/04E, HKUST6275/04E and HKUST6165/05E, a grant from NSFC/RGC under the contract N_HKUST605/02, a grant from NSF China under the contract 60429202.     

An algorithm for computing a Padé approximant with minimal degree denominator

In this paper, a new definition of a reduced Padé approximant and an algorithm for its computation are proposed. Our approach is based on the investigation of the kernel structure of the Toeplitz matrix. It is shown that the reduced Padé approximant always has nice properties which the classical Padé approximant possesses only in the normal case. The new algorithm allows us to avoid the appearance of Froissart doublets induced by computer roundoff in the non-normal Padé table.     

Irrationality proof of certain Lambert series using little q-Jacobi polynomials

We apply the Padé technique to find rational approximations to