Function approximation, integration, and optimization are three fundamental mathematical problems. They are especially challenging when the functions involved fluctuate wildly in certain parts of the domain, or if the domain is high dimensional. Ideally, algorithms to solve these problems should possess a rigorous mathematical framework, data-based (probabilistic) error bounds, and advanced sampling strategies for efficiency.

The Guaranteed Automatic Integration Library (GAIL) is our multi-year research effort addressing these aforementioned challenges. GAIL is a free, open-source MATLAB software library with nine main algorithms undergirded by over a dozen peer-reviewed publications. GAIL solves problems in univariate and multivariate integration, and in univariate function approximation and optimization. GAIL algorithms adaptively sample data values of the input function and automatically stop when the error tolerance has been reached. In some cases, GAIL algorithms are proven to have asymptotically optimal computational cost. We consistently employ good software development practices for GAIL such as unit tests, searchable online documentation, and Git version control. GAIL is available at

Function approximation, integration, and optimization are fundamental problems requiring numerical solutions that come from iterative algorithms. A crucial question is how and when to stop the computation.

Theoretical error bounds typically contain unknown quantities, such as the norm of the input function. This makes them impractical as stopping criteria.

Therefore, practical algorithms that adapt the computation to the error requirement are often based on heuristics. These include a popular adaptive quadrature algorithm of Shampine [

To address these shortcomings, we have developed adaptive stopping criteria for univariate function approximation, integration, and optimization; and for multivariate integration. We have implemented them in the Guaranteed Automatic Integration Library (GAIL) [

The underlying idea in our GAIL algorithms is that for reasonable functions

GAIL includes the following algorithms. All core algorithm names end with “_g” to denote some form of accuracy

Structure of GAIL Algorithms.

One-dimensional algorithms:

Multi-dimensional algorithms:

a real-valued function,

its domain,

user tolerance,

an initial number and a maximum number of sample points in _{0},

a maximum number of sample points _{N}

a maximum number of iterations,

GAIL architectural design. The largest yellow circle contains a compulsory input function _{i}_{i}_{i}_{i}

Among all the inputs, only _{a}_{r}_{a}_{r}

In the _{i}_{i}_{i}_{i}_{l}, e = e_{l}_{i}_{N}

Each one of our key GAIL algorithms, except for

Ordered input values:

Input structure array:

Ordered input values, followed by optional name-value pairs:

For

We note that almost all high-dimensional integration algorithms in GAIL have been re-implemented (with extensions) in the open-source Python software library, QMCPy [

In the following, we showcase GAIL’s performance with two examples on univariate function optimization and cubature.

We plot the function ^{–6}. In addition,

Function

Performance of

METHOD | |||
---|---|---|---|

| |
1.0 × 10^{–10} |
0.5 | 1.0 × 10^{–8} |

| |
0 | 4.0 | 1.3 × 10^{–7} |

113 | 10 | 37 | |

Time (seconds) | 0.042 | 0.048 | 0.022 |

Essential code in the MATLAB script,

where

Average performance of cubatures with automatic stopping criteria for estimating the integrals in (2) for 1000 independent runs. These results can be conditionally reproduced with the MATLAB command,

METHOD | MC | LATTICE | SOBOL | BAYES LATTICE | BAYES NET |
---|---|---|---|---|---|

Absolute Error | 1.1 × 10^{–3} |
5.2 × 10^{–4} |
5.2 × 10^{–4} |
3.4 × 10^{–7} |
5.8 × 10^{–4} |

Tolerence Met | 100% | 100% | 100% | 100% | 100% |

2500000 | 4100 | 3900 | 4100 | 1800 | |

Time (seconds) | 0.1700 | 0.0097 | 0.0065 | 0.0100 | 0.1200 |

Absolute Error | 1.2 × 10^{–2} |
1.4 × 10^{–2} |
6.9 × 10^{–3} |
2.1 × 10^{–1} |
8.8 × 10^{–3} |

Tolerence Met | 100% | 99% | 100% | 98% | 100% |

7400000 | 15000 | 16000 | 1000000 | 8200 | |

Time (seconds) | 1.1000 | 0.0380 | 0.0240 | 2.4000 | 0.3600 |

Essential code in the MATLAB script,

The testing of GAIL library is automated as scheduled tasks. There are two kinds of tests run: fast tests and long tests.

As aptly named, the fast tests take a relatively short time to run so that a user can quickly test the sanity of the library and the installation. Essential capabilities of the algorithms are quickly checked with carefully chosen tests to make sure the new code has not broken existing algorithms.

The long tests are more rigorous use cases that take much longer time, up to several hours to finish. These tests also typically include the examples from the papers and theses associated with the GAIL algorithms. The long tests are meant to test all the features and capabilities of the algorithms which cannot be covered in the fast tests.

Both types of tests are executed on the Karlin computing cluster hosted at the Illinois Institute of Technology (IIT). These machines run Centos Release 6.10. The Portable Batch System (PBS) is used to schedule the tasks. GAIL library is tested with seven recent MATLAB versions at least. The fast tests are automatically run once everyday.

The fast tests take less than two minutes to finish in our test setup. The long tests are run everyday for at least one version of MATLAB so that all the recent seven MATLAB release versions are covered in a circular rotation. As of this writing, both the fast tests and long tests are run with these MATLAB versions: R2017a, R2017b, R2018a, R2018b, R2019a, R2019b, and R2020a.

Before the tests begin, the ‘develop’ branch of the GAIL git repository is pulled in. Then the fast tests are run first, followed by the long tests. Automatically the test results are sent as emails to the maintainers.

All of the GAIL code-base is hosted and version-controlled in GitHub at

Our software is expected to run on multiple operating systems including but not limited to Windows, Mac, and Linux. Any operating system that is compatible with the MATLAB versions below should be able to run GAIL successfully; please see System Requirements and Supported Compilers at

MATLAB, versions R2017a–R2021a.

We refer readers to the following page for MATLAB system requirements, which depend on MATLAB version and machine type:

In addition, the installation of GAIL requires approximately 42 megabytes (MB) of disk space. The memory requirement of executing GAIL applications depends on various factors such as choice of algorithms, user tolerance, and the number of function sampling points. We recommend at least 2 gigabytes (GB) of memory allocated for MATLAB and GAIL.

GAIL is developed in MATLAB versions R2016a to R2021a. In particular, three of our core algorithms,

For development and testing purposes, we use the third-party toolboxes, Chebfun [

We thank the contributions of current, former, and visiting students in the Department of Applied Mathematics at Illinois Institute of Technology: Noah Grudowski, Cu Hauw Hung, Yueyi Li, Xincheng Sheng, Aleksei Sorokin, Xiaoyang Zhao, and Tianci Zhu.

English

GAIL is publicly available as a Git repository hosted on GitHub at

Users with questions can submit an issue through GitHub Issues. Developers who wish to add algorithms to or enhance GAIL can submit a pull request, or email to the mailing list,

The additional files for reproducing the results in

Hickernell, Ding, and Choi wish to thank students from the following IIT courses for discussion: SCI 498 Adaptive Monte Carlo Algorithms with Applications to Financial Risk Management, Summer 2016; MATH 491 Reading & Research, Summer 2015; SCI 498/MATH 491 Computational Social Sciences, Summer 2016; MATH 491-195 Solving Problems in the Social Sciences Using Tools from Computational Mathematics and Statistics, Summer 2015; Math 573/SCI 498 Reliable Mathematical Software, Fall 2013 and Fall 2018.

Our work is supported in part by grants NSF-DMS-1115392 and NSF-DMS-1522687. The publication costs for this article were funded by a gift from a generous Illinois Institute of Technology alumnus.

The authors have no competing interests to declare.