Paper VIII: Packet Operator Algorithms, Exact Compilation, and GPU Realization

Download original file

This is the original source text. Reading it does not run or verify the program.

Read the typeset paper

1 @book{Bellman1957,
2   author    = {Richard Bellman},
3   title     = {Dynamic Programming},
4   publisher = {Princeton University Press},
5   address   = {Princeton, NJ},
6   year      = {1957}
7 }
8 
9 @book{GolubVanLoan2013,
10   author    = {Gene H. Golub and Charles F. Van Loan},
11   title     = {Matrix Computations},
12   edition   = {Fourth},
13   publisher = {Johns Hopkins University Press},
14   address   = {Baltimore, MD},
15   year      = {2013}
16 }
17 
18 @book{Higham2002,
19   author    = {Nicholas J. Higham},
20   title     = {Accuracy and Stability of Numerical Algorithms},
21   edition   = {Second},
22   publisher = {Society for Industrial and Applied Mathematics},
23   address   = {Philadelphia, PA},
24   year      = {2002},
25   doi       = {10.1137/1.9780898718027}
26 }
27 
28 @book{Saad2003,
29   author    = {Yousef Saad},
30   title     = {Iterative Methods for Sparse Linear Systems},
31   edition   = {Second},
32   publisher = {Society for Industrial and Applied Mathematics},
33   address   = {Philadelphia, PA},
34   year      = {2003},
35   doi       = {10.1137/1.9780898718003}
36 }
37 
38 @book{Davis2006,
39   author    = {Timothy A. Davis},
40   title     = {Direct Methods for Sparse Linear Systems},
41   publisher = {Society for Industrial and Applied Mathematics},
42   address   = {Philadelphia, PA},
43   year      = {2006},
44   doi       = {10.1137/1.9780898718881}
45 }
46 
47 @article{Hager1989,
48   author  = {William W. Hager},
49   title   = {Updating the Inverse of a Matrix},
50   journal = {SIAM Review},
51   volume  = {31},
52   number  = {2},
53   pages   = {221--239},
54   year    = {1989},
55   doi     = {10.1137/1031049}
56 }
57 
58 @article{EckartYoung1936,
59   author  = {Carl Eckart and Gale Young},
60   title   = {The Approximation of One Matrix by Another of Lower Rank},
61   journal = {Psychometrika},
62   volume  = {1},
63   number  = {3},
64   pages   = {211--218},
65   year    = {1936},
66   doi     = {10.1007/BF02288367}
67 }
68 
69 @article{Mirsky1960,
70   author  = {Leon Mirsky},
71   title   = {Symmetric Gauge Functions and Unitarily Invariant Norms},
72   journal = {The Quarterly Journal of Mathematics},
73   series  = {2},
74   volume  = {11},
75   pages   = {50--59},
76   year    = {1960},
77   doi     = {10.1093/qmath/11.1.50}
78 }
79 
80 @article{BunchNielsen1978,
81   author  = {James R. Bunch and Christopher P. Nielsen},
82   title   = {Updating the Singular Value Decomposition},
83   journal = {Numerische Mathematik},
84   volume  = {31},
85   pages   = {111--129},
86   year    = {1978},
87   doi     = {10.1007/BF01397471}
88 }
89 
90 @article{GolubKahan1965,
91   author  = {Gene H. Golub and William Kahan},
92   title   = {Calculating the Singular Values and Pseudo Inverse of a Matrix},
93   journal = {Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis},
94   volume  = {2},
95   number  = {2},
96   pages   = {205--224},
97   year    = {1965},
98   doi     = {10.1137/0702016}
99 }
100 
101 @article{CoifmanWickerhauser1992,
102   author  = {Ronald R. Coifman and Mladen Victor Wickerhauser},
103   title   = {Entropy Based Algorithms for Best Basis Selection},
104   journal = {IEEE Transactions on Information Theory},
105   volume  = {38},
106   number  = {2},
107   pages   = {713--718},
108   year    = {1992},
109   doi     = {10.1109/18.119732}
110 }
111 
112 @inproceedings{HongKung1981,
113   author    = {Jia Wei Hong and H. T. Kung},
114   title     = {I O Complexity: The Red Blue Pebble Game},
115   booktitle = {Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing},
116   pages     = {326--333},
117   publisher = {Association for Computing Machinery},
118   year      = {1981},
119   doi       = {10.1145/800076.802486}
120 }
121 
122 @article{WilliamsWatermanPatterson2009,
123   author  = {Samuel Williams and Andrew Waterman and David Patterson},
124   title   = {Roofline: An Insightful Visual Performance Model for Multicore Architectures},
125   journal = {Communications of the ACM},
126   volume  = {52},
127   number  = {4},
128   pages   = {65--76},
129   year    = {2009},
130   doi     = {10.1145/1498765.1498785}
131 }
132 
133 @article{BallardDemmelHoltzSchwartz2011,
134   author  = {Grey Ballard and James Demmel and Olga Holtz and Oded Schwartz},
135   title   = {Minimizing Communication in Numerical Linear Algebra},
136   journal = {SIAM Journal on Matrix Analysis and Applications},
137   volume  = {32},
138   number  = {3},
139   pages   = {866--901},
140   year    = {2011},
141   doi     = {10.1137/090769156}
142 }
143 
144 @article{HalkoMartinssonTropp2011,
145   author  = {Nathan Halko and Per Gunnar Martinsson and Joel A. Tropp},
146   title   = {Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions},
147   journal = {SIAM Review},
148   volume  = {53},
149   number  = {2},
150   pages   = {217--288},
151   year    = {2011},
152   doi     = {10.1137/090771806}
153 }
154 
155 @article{MartinssonTropp2020,
156   author  = {Per Gunnar Martinsson and Joel A. Tropp},
157   title   = {Randomized Numerical Linear Algebra: Foundations and Algorithms},
158   journal = {Acta Numerica},
159   volume  = {29},
160   pages   = {403--572},
161   year    = {2020},
162   doi     = {10.1017/S0962492920000021}
163 }
164 
165 @article{DavisKahan1970,
166   author  = {Chandler Davis and William M. Kahan},
167   title   = {The Rotation of Eigenvectors by a Perturbation. III},
168   journal = {SIAM Journal on Numerical Analysis},
169   volume  = {7},
170   number  = {1},
171   pages   = {1--46},
172   year    = {1970},
173   doi     = {10.1137/0707001}
174 }
175 
176 @article{CarsonHigham2018,
177   author  = {Erin Carson and Nicholas J. Higham},
178   title   = {Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions},
179   journal = {SIAM Journal on Scientific Computing},
180   volume  = {40},
181   number  = {2},
182   pages   = {A817--A847},
183   year    = {2018},
184   doi     = {10.1137/17M1140819}
185 }
186 
187 @article{Strassen1969,
188   author  = {Volker Strassen},
189   title   = {Gaussian Elimination Is Not Optimal},
190   journal = {Numerische Mathematik},
191   volume  = {13},
192   pages   = {354--356},
193   year    = {1969},
194   doi     = {10.1007/BF02165411}
195 }
196 
197 @article{DemmelHoltzSchwartz2007,
198   author  = {James Demmel and Ioana Dumitriu and Olga Holtz},
199   title   = {Fast Linear Algebra Is Stable},
200   journal = {Numerische Mathematik},
201   volume  = {108},
202   number  = {1},
203   pages   = {59--91},
204   year    = {2007},
205   doi     = {10.1007/s00211-007-0114-x}
206 }
207 
208 @article{AmbikasaranDarve2013,
209   author  = {Sivaram Ambikasaran and Eric Darve},
210   title   = {An O N Log N Fast Direct Solver for Partial Hierarchically Semi Separable Matrices},
211   journal = {Journal of Scientific Computing},
212   volume  = {57},
213   number  = {3},
214   pages   = {477--501},
215   year    = {2013},
216   doi     = {10.1007/s10915-013-9714-z}
217 }
218 
219 @article{CooleyTukey1965,
220   author  = {James W. Cooley and John W. Tukey},
221   title   = {An Algorithm for the Machine Calculation of Complex Fourier Series},
222   journal = {Mathematics of Computation},
223   volume  = {19},
224   number  = {90},
225   pages   = {297--301},
226   year    = {1965},
227   doi     = {10.1090/S0025-5718-1965-0178586-1}
228 }
229 
230 @article{Oseledets2011,
231   author  = {Ivan V. Oseledets},
232   title   = {Tensor Train Decomposition},
233   journal = {SIAM Journal on Scientific Computing},
234   volume  = {33},
235   number  = {5},
236   pages   = {2295--2317},
237   year    = {2011},
238   doi     = {10.1137/090752286}
239 }
240 
241 @inproceedings{FrigoLeisersonProkopRamachandran1999,
242   author    = {Matteo Frigo and Charles E. Leiserson and Harald Prokop and Sridhar Ramachandran},
243   title     = {Cache Oblivious Algorithms},
244   booktitle = {Proceedings of the Fortieth Annual Symposium on Foundations of Computer Science},
245   pages     = {285--297},
246   publisher = {IEEE Computer Society},
247   year      = {1999},
248   doi       = {10.1109/SFFCS.1999.814600}
249 }
250 
251 @manual{NVIDIA2026,
252   author       = {{NVIDIA Corporation}},
253   title        = {CUDA C++ Programming Guide},
254   organization = {NVIDIA Corporation},
255   note         = {Archive version 12.8.1, Section 3.2.8.7 (CUDA Graphs), accessed 6 October 2026},
256   url          = {https://docs.nvidia.com/cuda/archive/12.8.1/cuda-c-programming-guide/index.html#cuda-graphs}
257 }
258 
259 @misc{IEEE7542019,
260   author       = {{IEEE Standards Association}},
261   title        = {IEEE Standard for Floating Point Arithmetic},
262   howpublished = {IEEE Std 754 2019},
263   year         = {2019},
264   doi          = {10.1109/IEEESTD.2019.8766229}
265 }
266 
267 @misc{HighamMary2021,
268   author = {Higham, Nicholas J. and Mary, Theo},
269   title = {Mixed Precision Algorithms in Numerical Linear Algebra},
270   year = {2021},
271   note = {MIMS EPrint 2021.20, Sections 3--4; classical real dot-product forward-error model},
272   url = {https://eprints.maths.manchester.ac.uk/2841/1/paper_eprint.pdf}
273 }

Back to source controls

Back to Paper VIII: Packet Operator Algorithms, Exact Compilation, and GPU Realization