Error analysis of Abate--Whitt methods for Inverse Laplace Transforms and a new algorithm for queuing theory applications

Basic Information

• Paper ID: 2510.14799
• Title: Error analysis of Abate--Whitt methods for Inverse Laplace Transforms and a new algorithm for queuing theory applications
• Authors: Nikita Deniskin (Scuola Normale Superiore), Federico Poloni (Università di Pisa)
• Classification: math.NA cs.NA (Numerical Analysis)
• Submission Date: October 16, 2024 to arXiv
• Paper Link: https://arxiv.org/abs/2510.14799

Abstract

This paper investigates the accuracy of Abate-Whitt methods for computing inverse Laplace transforms. These methods are based on evaluating linear combinations of a function $\hat{f}$ at a small number of points. The authors provide error bounds relating method accuracy to rational approximations of exponential functions and specialize the analysis to phase-type distributions in queuing theory and Markov-modulated fluid models. By employing the AAA algorithm, the authors propose a new family of methods called TAME, which significantly reduces the number of function evaluations while maintaining or improving accuracy.

Research Background and Motivation

Problem Definition

The inverse Laplace transform (ILT) is an important yet challenging numerical problem. Given the Laplace transform $\hat{f}(s) = \int_0^{\infty} e^{-st}f(t)dt$ of a function $f$, one must reconstruct values of $f(t)$ from evaluations of $\hat{f}$ at a few points.

Problem Significance

1. Ill-posedness: Unlike the Fourier transform, the inverse Laplace transform is an ill-posed problem; small errors in $\hat{f}$ can lead to large errors in $f(t)$
2. Practical Applications: Widely used in queuing theory, probability theory, and engineering, particularly in phase-type distribution analysis and fluid queue analysis
3. Computational Efficiency: Existing methods typically require numerous function evaluations to achieve satisfactory accuracy

Limitations of Existing Methods

• Euler Method: Uses equally-spaced nodes on a vertical line but exhibits slow convergence
• Talbot Method: Improves performance through contour deformation but can be numerically unstable in certain cases
• Gaver-Stehfest Method: Based on the Post-Widder formula but prone to numerical cancellation
• CME Method: Although stable, exhibits slow convergence and requires more function evaluations

Core Contributions

1. Theoretical Analysis: Establishes rigorous mathematical relationships between Abate-Whitt method accuracy and rational approximations of exponential functions
2. Error Bounds: Provides quantitative error bounds for SE-class, ME-class, and LS-class functions
3. TAME Algorithm: Proposes a new parameter selection strategy based on the AAA algorithm, significantly improving efficiency
4. Application-Specific Analysis: Provides specialized analysis for phase-type distributions and fluid queue models in queuing theory
5. Numerical Stability: Discusses numerical issues in floating-point arithmetic and provides solutions

Methodology Details

Problem Formulation

Given the Laplace transform $\hat{f}(s)$, the Abate-Whitt method approximates $f(t)$ through:

$f_N(t) = \sum_{n=1}^N \frac{w_n}{t} \hat{f}\left(\frac{\beta_n}{t}\right)$

where $(w_n, \beta_n)_{n=1}^N$ are weight and node parameters.

Core Theoretical Framework

Connection to Rational Approximation

The authors establish a key theoretical connection: the rational approximant of the Abate-Whitt method is $\hat{\rho}_N(-z) = \sum_{n=1}^N \frac{w_n}{\beta_n - z}$

Method accuracy directly depends on the quality of approximation of $e^z$ by $\hat{\rho}_N(-z)$.

Function Classes

The paper focuses on three classes of "tame" functions:

1. SE-class (Exponential Sums): $f(t) = \sum_{m=1}^M c_m e^{\alpha_m t}$
2. ME-class (Matrix Exponential): $f(t) = v^* \exp(tQ)u$
3. LS-class (Laplace-Stieltjes): $f(t) = \int e^{-xt}d\mu(x)$

TAME Algorithm Design

AAA Algorithm Modifications

The authors make key modifications to the AAA algorithm:

1. Degree Adjustment: Ensures rational function degree is $(N-1,N)$ rather than $(K-1,K-1)$
2. Conjugate Pairs: Guarantees non-real weights and nodes appear in conjugate pairs
3. Numerical Stability: Runs main loop in binary 64-bit precision, using high precision only for eigenvalue problems

Domain Selection Strategy

Selects appropriate approximation domain $\Omega$ based on function type:

• Fluid Queues: $\Omega = B(-r,r)$, where $r = \lambda t$
• ME-class: $\Omega$ should contain $W(tQ)$ (numerical range)
• LS-class: $\Omega = [-L,0]$

Experimental Setup

Experimental Design

The authors design five experiments to validate the TAME method:

Experiment A: Fluid queue model ($d_+ = 5, d_- = 10$, uniformization rate $\lambda = 1$) Experiment B: Performance comparison at different time points Experiment C: Continuous-time Markov chain ($d = 15$) Experiment D: Non-smooth signals (triangular and square waves) Experiment E: European call option pricing

Comparison Methods

• Euler method
• Gaver-Stehfest method
• Talbot method
• CME method
• Zakian method

Evaluation Metrics

Primarily uses $L_{\infty}$ error: $\|f(t) - f_N(t)\|_{\infty}$

Experimental Results

Main Findings

Experiment A Key Discoveries

• TAME Efficiency: Requires only 3-4 function evaluations to achieve comparable or better accuracy than classical methods
• Numerical Stability: TAME does not exhibit numerical instability with increasing $N'$, whereas classical methods show error growth after reaching minimum error
• Optimal Performance:
  • CDF: TAME achieves error of $3.3 \times 10^{-14}$ at $N'=4$
  • PDF: TAME achieves error of $8.0 \times 10^{-14}$ at $N'=3$

Experiment B Domain Selection Verification

Confirms theoretical predictions: TAME accuracy decreases when $r < t$ and maintains high accuracy when $r \geq t$.

Ablation Studies

Comparison of different domains $\Omega$ validates the domain selection strategy. TAME methods constructed using bounds from Theorems 5.2-5.4 all perform well.

Theoretical Verification

Experiments verify the accuracy of theoretical error bounds and moment estimates, confirming consistency between rational approximation theory and practical performance.

Related Work

Development of Abate-Whitt Framework

• Abate & Whitt (2006): Establishment of unified framework
• Classical Methods: Development of Euler, Talbot, Gaver-Stehfest and other methods
• CME Method: Moment-optimization-based method by Telek et al.

Rational Approximation Theory

• AAA Algorithm: Breakthrough work by Nakatsukasa et al.
• Padé Approximation: Theoretical foundation of Zakian method
• Numerical Stability: Precision issues in floating-point arithmetic

Conclusions and Discussion

Main Conclusions

1. Theoretical Breakthrough: First establishes rigorous mathematical relationships between Abate-Whitt method accuracy and rational approximation quality
2. Practical Algorithm: TAME method significantly reduces computational burden while maintaining accuracy
3. Numerical Stability: Resolves numerical instability issues of classical methods
4. Specialized Applications: Provides optimized parameter selection strategies for queuing theory applications

Limitations

1. Function Class Restrictions: Methods primarily applicable to "tame" function classes (SE, ME, LS)
2. Domain Dependence: Requires prior knowledge to select appropriate approximation domain $\Omega$
3. Non-smooth Functions: For discontinuous functions (e.g., square waves), CME method may perform better
4. Theoretical Constants: The constant $1+\sqrt{2}$ in the Crouzeix-Palencia theorem may not be tight

Future Directions

1. Extended Function Classes: Extend theory to broader function classes
2. Adaptive Domain Selection: Develop algorithms for automatic optimal $\Omega$ selection
3. Weight Optimization: Further optimize weight selection to avoid excessive growth
4. Parallel Algorithms: Develop parallel versions for large-scale problems

In-Depth Evaluation

Strengths

1. Theoretical Depth: Establishes rigorous mathematical framework, filling important theoretical gaps
2. Practical Value: TAME method demonstrates excellent performance in practical applications, particularly in queuing theory
3. Numerical Insights: Provides in-depth analysis of floating-point effects with practical numerical stability solutions
4. Comprehensive Experiments: Covers diverse test cases both within and beyond theoretical function classes

Weaknesses

1. Scope of Applicability: While covering important function classes, still limited to specific categories
2. Parameter Tuning: Requires domain expertise to select appropriate domains and parameters
3. Fairness of Comparisons: Parameter settings for different methods in some experiments may not be entirely fair

Impact

1. Academic Contribution: Provides new theoretical perspective for numerical methods of inverse Laplace transforms
2. Practical Applications: Direct application value in queuing theory, financial mathematics, and other fields
3. Methodological Innovation: AAA algorithm application inspires approaches to other numerical problems

Applicable Scenarios

• Phase-type distribution analysis in queuing theory
• Markov-modulated fluid models
• Engineering applications requiring high-precision inverse Laplace transforms
• Scenarios with high function evaluation costs

References

This paper cites 49 important references covering classical and cutting-edge work in Laplace transform theory, numerical methods, matrix analysis, and queuing theory. Particularly noteworthy are comprehensive citations of the original Abate & Whitt work, the AAA algorithm, and related numerical methods.

Overall Assessment: This is a high-quality numerical analysis paper that successfully combines theoretical analysis with practical applications. The TAME method is not only theoretically well-founded but also demonstrates excellent practical performance. The paper's contributions are of significant value for both numerical computation of inverse Laplace transforms and queuing theory applications.