Three main class of algorithms: - Direct methods: compute exact solutions (up to machine error), relatively costly; - [[Iterative Algorithms|Iterative methods]]: iteratively refine solutions, usually take fewer iterations to reach machine error-level precision. - [[Randomized Algorithms|Randomized algorithms]]: reduce complexity with randomization, produce a good solution with high probability. | | Direct | Iterative | Randomized | | ---------------- | ---------------------------------------------------- | ------------------------------------------------ | --------------------------------------------------------------- | | Low-Rank Approx. | [[Singular Value Decomposition\|SVD w. Golub-Kahan]] | | [[Singular Value Decomposition#Randomized SVD\|Randomized SVD]] | | Linear Systems | [[LU Factorisation\|LU]], [[QR Factorisation\|QR]] | [[GMRES Algorithm\|GMRES]], [[CG Algorithm\|CG]] | | | Least Squares | [[QR Factorisation\|QR]] | | Sketch-and-solve, Blendenpik | | Eigenvalues | (ask Galois) | [[QR Algorithm\|QR Algo.]] | | ### Topics ![[NotesWithDomain.base#NonSnippets]] ### Snippets ![[NotesWithDomain.base#Snippets]]