Inclusion of AAA rational approximation in SciPy

Hi all,

I would like to propose that we add the AAA algorithm for rational approximation to SciPy. The method was introduced in 2018 by Nakatsukasa, Sète, and Trefethen in the paper “The AAA algorithm for rational approximation”. Since then the paper has been cited approximately 400 times.

The method performs approximation by rational functions on an arbitrary real or complex set of points. It differs from other techniques in that it represents the rational approximant in barycentric form and selects support points greedily to avoid instabilities. As well as evaluating the approximation, it is also easy to compute its zeros and poles/residues. It has been used in a wide variety of applications many of which are summarized in “The first five years of the AAA algorithm”.

I have already implemented a pure Python version of the method as part of my master’s thesis at the University of Oxford under the supervision of Prof. Nakatsukasa and @izaid, so I do not believe it would require too much work to incorporate. The AAA algorithm forms a part of a method we hope may be included in scipy.optimize which finds the poles and zeros of a given function. However, we believe AAA would be a valuable addition to SciPy in its own right. I would propose that AAA would live under scipy.interpolate. Whilst the method does not strictly satisfy the interpolation property, the selected support points do interpolate the function that is being approximated. Furthermore, we already have another method for rational approximation, Padé, in scipy.interpolate.

Whilst there are some existing Python implementations of the AAA algorithm, see https://github.com/c-f-h/aaa, https://github.com/c-f-h/baryrat, and https://github.com/abigopal/aaapy, most of these implementations are based on the original paper rather than the improvements that have been made as a part of the Chebfun package. Furthermore, some of these implementations lack the good documentation, stringent testing, etc, that come with most of the functions we include in SciPy.

One query that would be helpful to resolve is licensing. In writing my code I referred to the Chebfun source code. This appears to be suitably permissively licensed for SciPy, see here, however, it is a non-standard license so it would be helpful to confirm this.

Please feel free to share any thoughts or questions below.

Regards,
Jake

1 Like

Hi Jake,

This sounds like a useful addition of a well-established method. The subpackage names are broad categories to collect related algorithms, so interpolate, even if not 100% accurate, seems fine. The chebfun license looks like 3-clause BSD, so should pose no problem. If you feel you borrowed substantial ideas, I’d include attribution to their code (or, perhaps do that either way to be safe).

Thanks for this contribution!

1 Like