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 Factorization\|QR]] | [[GMRES Algorithm\|GMRES/CG]] | |
| Least Squares | [[QR Factorization\|QR]] | | Sketch-and-solve, Blendenpik |
| Eigenvalues | (ask Galois) | [[QR Algorithm\|QR Algo.]] | |
> [!citenotitle]
>
> ```dataview
> table without id
> File as "Topics",
> choice(oneliner, oneliner, "") as "",
> dateformat(file.mtime, "yyyy-MM-dd") as "Last Modified"
> from ""
> FLATTEN "[[" + file.path + "|" + truncate(file.name, 30) + "]]" as File
> where
> (
> (domain and contains(domain, this.file.link)
> and (file.name != this.file.name))
> or
> any(map(file.tags,
> (x) => econtains(this.domain_tags, substring(x, 1))))
> or
> any(map(file.tags,
> (x) => any(map(this.domain_tags,
> (domtag) => contains(x, domtag + "/")))
> ))
> )
> and
> !contains(file.path, "2 - Snippets")
> and
> !contains(file.tags, "subdomain")
> sort file.mtime desc
> ```
>
> [!citenotitle]
>
> ```dataview
> table without id
> File as "Snippets",
> choice(oneliner, oneliner, "") as "",
> dateformat(file.mtime, "yyyy-MM-dd") as "Last Modified"
> from "2 - Snippets"
> FLATTEN "[[" + file.path + "|" + truncate(file.name, 30) + "]]" as File
> where
> (
> (domain and contains(domain, this.file.link)
> and (file.name != this.file.name))
> or
> any(map(file.tags,
> (x) => econtains(this.domain_tags, substring(x, 1))))
> or
> any(map(file.tags,
> (x) => any(map(this.domain_tags,
> (domtag) => contains(x, domtag + "/")))
> ))
> )
> sort file.mtime desc
> ```
## References and Credits
Trefethen and Bau's *Numerical Linear Algebra* ([on SOLO](https://solo.bodleian.ox.ac.uk/permalink/f/n28kah/oxfaleph012273464))
* Illustration of the SVD is Fig. 4.1.
* Illustration of the Householder reflection is Fig. 10.1.
Gilbert Strang's linear algebra videos on [MIT OCW](https://www.youtube.com/@mitocw) are extremely helpful for understanding GE, SVD, and QR decomposition.
* I learned more from MIT OCW than from the lectures. I should ask MIT for my degree.