"The World" of CLV

半年前退坑的我大概也想不到终于有一天我会遗忘这些基础技艺并且会重返$\text{Rendering}$

挺难理解的一次实验

代码量最小的一集

恭喜计网$\text{Lab}-2$成为我的博客里第一篇本校实验

提醒：本博客含有$\text{AI}$辅助创作内容

多重网格法是$\text{Graphics}$从业者的标配。——胡渊鸣

平时遇到的琐碎的$\text{C++}$稀奇古怪的知识，稀奇古怪的邪道和稀奇古怪的黑魔法。

虽然$\text{C++}$麻烦得雅痞，但还是得靠它吃饭啊。

最近更新速度比我想的要快，这就出第三篇了。。。也就是稀疏矩阵的直接求解方法。

上一篇讲过了矩阵的一些迭代求解方法，这些方法可以很自然地应用于稀疏矩阵中。然而直接方法就并非如此了。通常，直接方法将矩阵分解为三角阵的乘积（这一步必然是立方复杂度），分别求解。然而，稀疏矩阵的规模巨大，直接套用稠密矩阵的做法并没有充分利用稀疏性，效率必然很低，还有可能导致分解之后退化为稠密矩阵。因此稀疏矩阵求解的直接方法往往比迭代方法复杂很多。

整个话题相当庞杂，因此这篇文章也是长期更新。但是显然我没有那么多工夫去天天折腾数值算法所以说不准哪天本文就永远停更了

这个系列的第二篇从上学期鸽到现在。。。

线性代数最基本的问题就是解线性系统了，但是这也是个很不$\text{trivial}$的问题。

求解线性系统，主要有两类方法，直接求解（分解）或者迭代方法。对于大型稀疏矩阵而言，两种方法各有优势，都有不少深入的文献和代码可以学习。这次简要介绍求解线性系统的迭代方法，直接方法留到这个系列的第三篇（又不知道会鸽到什么时候了，大悲）。

迭代法是一个很大的话题，也有一些专著，比如$\text{Yousef Saad}$($\text{GMRES}$方法的发明者)的书$\text{Iterative Methods for Sparse Linear Systems}$。这次不仅参考了这本书，同时也参考了徐树方的数值线性代数。当然，由于内容丰富不可能一下子学完，这篇小水文也会随着我的继续学习长期更新写完共轭梯度就咕咕。

计算理论课上讲上下文无关文法的时候跳过了这一部分。但是看起来这一块恰恰对编译原理相当重要。

所以浅浅看下书上这部分的内容，顺便跟编译原理联系联系。

书接上回：UCSD-CSE272-部分作业1和作业2。做完正式作业以后自然还剩下今年的$\text{Final Project}$，也就是从给定的列表中选择一个算法并且学习实现，或者选择一个研究题目。

上回结尾没说要做大作业啊？不是说去做模拟吗？两者同步推进不是更好嘛！

作为双向光传输算法的入门门槛，双向路径追踪是必须学习的基础，也算是$\text{Rendering}$的入门门槛，因此首先从此开始当然这是闫令琪的意见。

在$\text{CSE272}$的$\text{Hw-2}$中，我们分$6$步由易到难逐步完善算法，最终实现了完整的体积路径追踪。这种方法确实非常有效，因此对于本次$\text{Final Project}$，我也打算用类似的方式，由易到难，逐步完善。