George Labahn

Bernhard Beckermann, George Labahn, Ana C. Matos

In this paper we consider the problem of working with rational functions in a numeric environment. A particular problem when modeling with such functions is the existence of Froissart doublets, where a zero is close to a pole. We discuss three different parameters which allow one to monitor the absence of Froissart doublets for a given general rational function. These include the euclidean condition number of an underlying Sylvester-type matrix, a parameter for determing coprimeness of two numerical polynomials and bounds on the spherical derivative. We show that our parameters sharpen those found in a previous paper by two of the autours.

Ziwen Wang, Stavros Birmpilis, George Labahn et al.

We describe a C implementation of the Las Vegas algorithm of Birmpilis, Labahn and Storjohann from 2020 for computing the Smith normal form of a nonsingular integer matrix. The algorithm computes a Smith massager for the input matrix using $O(n^ω\, \B(\log n + \log \|A\|)\, (\log n)^2)$ bit operations, which is softly equivalent to the cost of multiplying two matrices of the same dimension and entry size. We describe the key implementation techniques that bridge the gap between the theoretical algorithm and practical performance, including BLAS-accelerated modular arithmetic via the Residue Number System and an adaptive batching scheme that collapses the theoretical $O(\log n)$ iterations to $O(1)$ in practice. Experiments on matrices of dimension up to $n = 10007$ show that the implementation's running time scales proportionally to that of a single BLAS matrix multiplication, with both exhibiting the same effective growth rate on a log-log plot.

Peter A. Forsyth, George Labahn

The decumulation of a defined contribution (DC) pension plan is well known to be one of the hardest problems in finance. We model this decumulation challenge as an optimal stochastic control problem. The control problem is solved, at each rebalancing date, by alternatively solving a linear partial-integro differential equation (PIDE) followed by an optimization step. We solve the PIDE by using a $δ$-monotone Fourier method, which ensures that monotonicity holds to $O(δ)$. We allow for the use of leverage (i.e. borrowing to invest in stocks), as well as minimum constraints on bond holdings. We pay particular attention to minimizing wrap-around error, an issue which is endemic for Fourier methods and central to the effective use of these methods for optimal control problems. Rather unexpectedly, we find that restricting the portfolio equity fraction to a maximum of 50\% does not reduce portfolio efficiency noticeably. This may be a useful strategy for risk-averse retirees.

George Labahn, Arne Storjohann

Given a full column rank $M \in \Z^{\ell \times m}$ and an $F \in \Z^{n \times m}$ we present an algorithm to compute the $n \times n$ basis in Hermite form of the integer lattice comprised of all rows $p \in \Z^{1 \times n}$ such that $pF \in \Z^{1 \times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the algorithm uses about the same number of bit operations as required to multiply together two matrices of the same dimension and size of entries as $M$.

Parsiad Azimzadeh, Erhan Bayraktar, George Labahn

In [Azimzadeh, P., and P. A. Forsyth. "Weakly chained matrices, policy iteration, and impulse control." SIAM J. Num. Anal. 54.3 (2016): 1341-1364], we outlined the theory and implementation of computational methods for implicit schemes for Hamilton-Jacobi-Bellman quasi-variational inequalities (HJBQVIs). No convergence proofs were given therein. This work closes the gap by giving rigorous proofs of convergence. We do so by introducing the notion of nonlocal consistency and appealing to a Barles-Souganidis type analysis. Our results rely only on a well-known comparison principle and are independent of the specific form of the intervention operator.

Scott MacLean, George Labahn

Recognizing handwritten mathematics is a challenging classification problem, requiring simultaneous identification of all the symbols comprising an input as well as the complex two-dimensional relationships between symbols and subexpressions. Because of the ambiguity present in handwritten input, it is often unrealistic to hope for consistently perfect recognition accuracy. We present a system which captures all recognizable interpretations of the input and organizes them in a parse forest from which individual parse trees may be extracted and reported. If the top-ranked interpretation is incorrect, the user may request alternates and select the recognition result they desire. The tree extraction step uses a novel probabilistic tree scoring strategy in which a Bayesian network is constructed based on the structure of the input, and each joint variable assignment corresponds to a different parse tree. Parse trees are then reported in order of decreasing probability. Two accuracy evaluations demonstrate that the resulting recognition system is more accurate than previous versions (which used non-probabilistic methods) and other academic math recognizers.