Improving Matrix Exponential for Generative AI Flows: A Taylor-Based Approach Beyond Paterson--Stockmeyer
Authors: Jorge Sastre, Daniel Faronbi, José Miguel Alonso, Peter Traver, Javier Ibáñez, Nuria Lloret
Organizations: Universitat Politècnica de València, Spain; aInstituto de Telecomunicaciones y Aplicaciones Multimedia · eMusic and Audio Research Lab, New York University, New York, USA · Universitat Politècnica de València, Spain; bInstituto de Instrumentación para Imagen Molecular · Universitat Politècnica de València, Spain; cInstituto de Matemática Multidisciplinar · Universitat Politècnica de València, Spain; dInstituto de Diseño para la Fabricación y Producción Automatizada
The matrix exponential is a fundamental operator in scientific computing and system simulation, with applications ranging from control theory and quantum mechanics to modern generative machine learning. While Padé approximants combined with scaling and squaring have long served as the standard, recent Taylor-based methods, which utilize polynomial evaluation schemes that surpass the classical Paterson--Stockmeyer technique, offer superior accuracy and reduced computational complexity. This paper presents an optimized Taylor-based algorithm for the matrix exponential, specifically designed for the high-throughput requirements of generative AI flows. We provide a rigorous error analysis and develop a dynamic selection strategy for the Taylor order and scaling factor to minimize computational effort under a prescribed error tolerance. Extensive numerical experiments demonstrate that our approach provides significant acceleration and maintains high numerical stability compared to existing state-of-the-art implementations. These results establish the proposed method as a highly efficient tool for large-scale generative modeling.
Figures & tables
Polynomial evaluation cost
3M
4M
5M
6M
7M
Approx. order m Paterson–Stockmeyer [ 11 ]
6
9
12
16
20
Approx. order m [ 12 ]
8
12
18
22
—
Approx. order m [ 19 ]
8
15+
21+
24
30
Padé evaluation cost
3.33M
4.33M
5.33M
6.33M
7.33M
Approx. order Padé method [ 20 , Tab. 2.2]
6
10
14
18
26
Mixed rational polynomial approx. cost
3.33M
4.33M
5.33M
6M
7M
Table 1: Cost and available order of approximation with the polynomial evaluation methods from Paterson–Stockmeyer [ 11 ] , Bader–Blanes–Casas [ 12 , Sec. 4] , Sastre–Ibáñez–Defez [ 19 , Sec. 3] , the Padé approximation method from Higham [ 20 , Tab. 2.2] and the mixed rational and polynomial approximation method from Sastre [ 9 , Tab. 3] .
c1
4.980119205559973 ×10−3
c2
1.992047682223989 ×10−2
c3
7.665265321119147 ×10−2
c4
8.765009801785554 ×10−1
c5
1.225521150112075 ×10−1
c6
2.974307204847627 ×100−
Table 2: Coefficients for the Taylor approximation of the matrix exponential of order m=8 , computed using formulas ( 13 ) and ( 14 )
c1
- 4.018761610201036 ×10−4
c9
- 2.224209172496374 ×100−
c2
- 2.945531440279683 ×10−3
c10
-5.792361707073261 ×100−
c3
-8.709066576837676 ×10−3
c11
-4.130276365929783 ×10−2
c4
- 4.017568440673568 ×10−1
c12
- 1.040801735231354 ×101−
c5
- 3.230762888122312 ×10−2
c13
-6.331712455883370 ×101−
c6
- 5.768988513026145 ×100−
c14
- 3.484665863364574 ×10−1
c7
- 2.338576034271299 ×10−2
c15
1
Table 3: Coefficients of y02 , y12 , and y22 from equations ( 15 )-( 17 ) used in the Taylor-based approximation of the matrix exponential of order m=15+ .
M
Computed W Power
Required Norms
Estimated Norms
1
W
∥W2∥1
∥W3∥1
∥W∥12
∥W∥13
2
W2
∥W3∥1
∥W4∥1
∥W2∥11⋅∥W∥1
∥W2∥11⋅∥W2∥1
4
W2
∥W5∥1
∥W6∥1
∥W2∥12⋅∥W∥1
∥W2∥12⋅∥W2∥1
6
W3
∥W7∥1
∥W8∥1
∥W3∥12⋅∥W∥1
∥W3∥12⋅∥W2∥1
9
W3
∥W10∥1
∥W11∥1
∥W3∥13⋅∥W∥1
∥W3∥13⋅∥W2∥1
12
W4
∥W13∥1
∥W14∥1
∥W4∥13⋅∥W∥1
∥W4∥13⋅∥W2∥1
Table 4: Computed powers of W , the corresponding norms required by ( 46 ), and their resulting approximations for each polynomial degree M considered in Algorithm 3.3 .
M
Computed W Power
Required Norms
Estimated Norms
1
W
∥W2∥1
∥W3∥1
∥W∥12
∥W∥13
2
W2
∥W3∥1
∥W4∥1
∥W2∥11⋅∥W∥1
∥W2∥11⋅∥W2∥1
4
W2
∥W5∥1
∥W6∥1
∥W2∥12⋅∥W∥1
∥W2∥12⋅∥W2∥1
8
W2
∥W9∥1
∥W10∥1
∥W2∥14⋅∥W∥1
∥W2∥14⋅∥W2∥1
even m
Wj
∥Wm+1∥1
∥Wm+2∥1
∥Wj∥1k⋅∥W∥1
∥Wj∥1k⋅∥W2∥1
15
W2
∥W16∥1
∥W17∥1
∥W2∥18
∥W2∥18⋅∥W∥1
Table 5: Computed powers of W , the norms required by ( 46 ), and their corresponding approximations for each polynomial degree M considered in Algorithm 3.3 . Note that j=2 for all degrees m>1 .
Figure 1: Experimental results for matrices in MCT and EMP sets.
Figure 2: Experimental results for the datasets.
Relative error
Products, opt15
Time (ms)
n
∥A∥1
opt15, 2−24
opt15, 10−8
torch
scipy
2−24
10−8
opt15
torch
16
1.85
2.5×10−8
2.5×10−8
9.9×10−8
6.2×10−8
4
4
0.14
0.34
64
6.14
5.7×10−8
1.7×10−7
6.6×10−7
1.4×10−7
4
5
0.15
0.37
128
11.69
1.2×10−7
1.2×10−7
5.2×10−7
2.4×10−7
5
5
0.16
0.35
256
22.97
1.5×10−7
1.5×10−7
7.3×10−7
4.6×10−7
6
6
0.18
0.38
512
44.82
5.0×10−7
5.0×10−7
2.5×10−6
8.9×10−7
7
7
0.20
0.40
Table 6: Relative error, number of matrix products and GPU execution time of expm_flow_opt15 (opt15), torch.linalg.matrix_exp (torch, [ 12 ] ) and scipy.linalg.expm (scipy, [ 18 ] ) in single precision. Execution times correspond to ε=2−24 for opt15.
Figure 3: Diagram overview of flow model trained to generate images.
Figure 4: Execution time (top) and speedup with respect to expm_flow (bottom) of the matrix exponential in single precision. (Left) A single n×n matrix, Intel CPU. (Right) A batch of N matrices of size 1024×1024 , NVIDIA L40S GPU; torch.linalg.matrix_exp ran out of GPU memory for N=1024 .
Function
Matrix products
Products per call
Ratio to expm_flow_opt15
expm_flow
265,856
8.66
1.96
expm_flow_opt15_fixed
154,346
5.02
1.14
expm_flow_opt15
135,711
4.42
1.00
Table 7: Matrix products required by each function during one epoch of the flow model on CIFAR-10, including initialization and testing ( 30,716 matrix exponentials).
Figure 5: Mean number of matrix products (left) and speedup of expm_flow_opt15 in number of products (right) as a function of the tolerance ε , with all functions using the same ε . The dotted vertical line marks ε=10−8 , the value used in the rest of the paper.
Products
Time of
Exponential,
Exponential,
Share of
Dataset
Function
per epoch
products (s)
forward (s)
total (s)
epoch
CIFAR-10
expm_flow
200,207
8.32
18.58
38.02
23%
expm_flow_opt15
101,411 (1.97)
4.78 (1.74)
11.57 (1.61)
25.13 (1.51)
14%
ImageNet32
expm_flow
5,134,832
271.3
642.8
1179.0
22%
expm_flow_opt15
2,592,426 (1.98)
118.1 (2.30)
275.3 (2.34)
620.8 (1.90)
15%
ImageNet64
expm_flow
5,147,683
451.0
777.9
2617.9
22%
Table 8: Matrix exponentials during training on an NVIDIA L40S GPU: matrix products per epoch, time spent in matrix products, time of the matrix exponential (forward pass, and forward plus backward pass), and share of the training time. Speedups with respect to expm_flow are given in parentheses.
Sample
1 sample
128 samples
expm_flow time
0.0373
0.0555
expm_flow_opt15 time
0.0305
0.0447
Speed-up
1.22
1.24
Table 9: Average inference times (in seconds) for sampling a matrix exponential variant of Glow on an NVIDIA L40S GPU. We compare the original expm_flow against expm_flow_opt15 for single and batched samples, including the calculated speedup factor.
Averaged weights
Raw weights
Dataset
expm_flow
expm_flow_opt15
expm_flow
expm_flow_opt15
CIFAR-10
3.3239
3.3244
3.3754
3.3670
ImageNet32
3.7851
3.7777
3.8506
3.8568
ImageNet64
3.4350
3.4346
3.4478
3.4473
Table 10: Test bits per dimension (lower is better) of the flow model trained with expm_flow and with expm_flow_opt15 , at the final epoch.
Averaged weights
Raw weights
Dataset
expm_flow
expm_flow_opt15
expm_flow
expm_flow_opt15
CIFAR-10
57.87
57.82
58.68
61.70
ImageNet32
59.68
57.86
65.08
60.08
ImageNet64
102.18
100.15
103.33
101.74
Table 11: FID (lower is better) between 10,000 samples of the flow model trained with each function and 10,000 images of the corresponding dataset, computed from the checkpoint with the lowest test BPD of the averaged weights.
Ratio
Mean
Median
Minimum
Maximum
α/ρ(W)
1.81
1.79
1.28
2.41
∥W∥1/ρ(W)
3.49
3.22
1.98
6.04
∥W∥1/α
1.91
1.83
1.36
2.71
Table 12: Value α from ( 51 ) compared with the spectral radius ρ(W) and with ∥W∥1 , for 2,044 weight matrices of the trained flow models.