Computational graphs for matrix functions

Jarlebring, Elias; Fasi, Massimiliano; Ringh, Emil

Abstract

Many numerical methods for evaluating matrix functions can be naturally viewed as computational graphs. Rephrasing these methods as directed acyclic graphs (DAGs) is a particularly effective approach to study existing techniques, improve them, and eventually derive new ones. The accuracy of these matrix techniques can be characterized by the accuracy of their scalar counterparts, thus designing algorithms for matrix functions can be regarded as a scalar-valued optimization problem. The derivatives needed during the optimization can be calculated automatically by exploiting the structure of the DAG in a fashion analogous to backpropagation. This article describes GraphMatFun.jl, a Julia package that offers the means to generate and manipulate computational graphs, optimize their coefficients, and generate Julia, MATLAB, and C code to evaluate them efficiently at a matrix argument. The software also provides tools to estimate the accuracy of a graph-based algorithm and thus obtain numerically reliable methods. For the exponential, for example, using a particular form (degree-optimal) of polynomials produces implementations that in many cases are cheaper, in terms of computational cost, than the Padé-based techniques typically used in mathematical software. The optimized graphs and the corresponding generated code are available online.

• Journal Article Type: Article
• Acceptance Date: Oct 17, 2022
• Online Publication Date: Mar 22, 2023
• Publication Date: Mar 22, 2023
• Deposit Date: Oct 29, 2022
• Journal: ACM Transactions on Mathematical Software
• Print ISSN: 0098-3500
• Electronic ISSN: 1557-7295
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 48
• Issue: 4
• Article Number: 39
• Pages: 1-35
• DOI: https://doi.org/10.1145/3568991
• Public URL: https://durham-repository.worktribe.com/output/1187194
• Related Public URLs: http://eprints.maths.manchester.ac.uk/2858/