INDEX

• Motivation: Padé Approximation
• MacLaurin Series of E[W]in GI/GI/1 Queue
• Padé Approximants
• Convergence of Padé Approximants
• Example
• Pole Distribution of Padé Approximant
• Rational Approximation for Integer- parameterized function
• Gregory-Newton series
• Newton-Padé Interpolation on Integer Points
• Cell Loss in ATM Multiplexers
• Rational Interpolation Based on Simulation
• Continuity of Rational Interepolants
• Quasi-Monte Carlo Analysis (Hlawka, 1971)
• Linear Congruential Pseudo RN
• Theorem (H. Niederreiter, 1976)
• QMC Analysis for Regenerative Simulation

Motivation: Padé Approximation

• Consider a formal (MacLaurin) series



The Padé Approximant is with

satisfying

• Coefficients of can be obtained from equating the coefficients of . (Linear equations)
• Coefficients of can be obtained from equating the coefficients of . (Linear equations)

back to contents

MacLaurin Series of in GI/GI/1 Queue

• Assume service time can be expressed as , where is i.i.d. with ,

and 's are independent of .

for some .

Interarrival density has a strictly proper rational Laplace transform;

• then we have

back to contents

Padé Approximants for

• Let the mean interarrival time be 1 and consider
1. ;
2. The asymptotics ;

we write

and approximate by an [M/M].

• Polynomial Approximation would not do well:

case:

back to contents

• Convergence concepts: uniform, in measure, in capacity.
• Capacity





For a compact set let be the planar Lebesque measure

However,

• Theorem (Nuttall-Pommerenke Theorem)

If

1. is analytic at zero
2. is analytic in

Then

for any compact set and



where is a sectorial sequence of Padé approximants.

back to contents

• in the queue



• in the queue

back to contents

Pole Distribution of Padé Approximant

• Example:

Note: has a branch cut and poles at 1, i and -i

back to contents

Rational Approximation for Integer- parameterized function (Rational Interpolation):

• Analyze asymptotic behavior when ;
• Find appropriate transformation based on the asymptotic behavior of ;
• Evaluate when is small;
• Calculate rational interpolants for ;
• Extrapolate for big 's.

back to contents

• Gregory-Newton series of is



where is -th order difference for .

• Theorem

(1)Gregory-Newton series converges in a half plane to a holomorphic function. The abscissa of convergence

(2) If then .

back to contents

• Theorem (following H. Wallin, 1979)

Let be analytic everywhere except at the infinity.

Let be the rational interpolant of type to with the interpolation points , .

Then, for any number ,



where ,

and the minimum distance from to the zeros of and the origin is .

• Outline of Proof

Consider instead the equivalent case when and is analytic everywhere except at the origin.

Let

and



so that is analytic in :

Also due to the analyticity of the integrand

Thus for ,

back to contents

• Dimension of the Markov Chain model:

State: with
- number of cells in the buffer
- number of voice sources in the ON state

• Number of states:


For K=500, N=100, c=48
number of states 50,000



• Computation time: (for K=500)

back to contents

• ATM Multiplexer with Heterogeneous Sources
• Number of states:
  For , , 128000 states
• For small , easy to do simulation

[4/3] RA:

back to contents

• ATM intree network

[4/3] GRA:

back to contents

• Theorem (Galluci and Johnes, 1976)

If

fits
fits

then

implies

for any compact set containing no poles of .

back to contents

If is Riemann integrable on , then



where

back to contents

Choose

• A large positive integer
• An integer with
• An integer
• 
• 

back to contents

Let M be a prime. Then,

for ,

back to contents

Let be regenerative with <IM

back to contents