数値計算の分野では、特定の構造を持つ行列方程式 \(Ax=b\) をいかに高速に解くかが常に重要なトピックです。 今回は、\(N = 2^n - 1\) のサイズを持つ Toeplitz 3重対角行列（対角成分が一定の行列）を対象に、定番の TDMA (Thomas Algorithm) アルゴリズムと、並列化に適した Cyclic Reduction (CR) アルゴリズムの性能を比較します。
驚くべきことに、並列化を行わないシングルスレッド環境においても、特定条件下では CR 法が TDMA よりも高速であるという結果が得られました。本記事ではそのアルゴリズムの詳細な仕組みとベンチマーク結果を紹介します。
Warning
この記事は Google Antigravity を使用して作成されました。 あくまで私自身の勉強した結果の備忘録としてのメモと思っていただければと思います。 （正確性はかならずしも担保されません。） 作成過程で知らないことが多くあり、非常に勉強になりました。
torchにはデフォルトでスプライン補間の実装がないなあと思い、自分で実装してみることにした。 正直こういったものは今だとLLMが勝手に実装を済ませてくれるものではある気がするので、どれくらい理論まで把握しておくべきかは悩ましいところではある。ただスプライン補間は基本的な数値計算の手法であるし、自分で実装してみることで理解を深めることが出来るので、一度はやってみるのも悪くはないかな、といったところ。 しょっぱなでtorchの話を書いたが、この記事ではnumpyとscipyのみを使ってスプライン補間を実装することにする。
ホモロジーゼミの中で位相の基底に関する議論が出てきたのでそれについてまとめます。 この記事は大部分が松坂の集合位相入門によっています。
ホモロジーゼミの基本群パートの一つの山場である、被覆空間の分類定理がやってきました。 この定理を示すためには、単連結な被覆空間の存在証明が必要になります。
Theorem: 単連結な被覆空間の存在
弧状連結かつ局所弧状連結な位相空間\(X,\tilde{X}\)で、\(\tilde{X}\)は\(X\)の被覆空間とする。\(\tilde{X}\)が単連結になるための必要十分条件は\(X\)が半局所単連結であることである。
Hatcherの"Algebraic Topology"のProposition 1.34でUnique lifting propertyとその証明が与えられているのですが、その証明がわかりにくかったのでここに分かりやすくまとめてみます。 Hatcherが全体的に読みにくいと感じるのは自分だけだろうか。。。
Hermite多項式の係数をpythonで求める方法を紹介します。
係数自体は三項間漸化式で求められますが、高次の係数を求めるときには再帰が必要になり計算量が増えてしまいます。
functoolsモジュールのcacheを使うと再帰を高速化できます。
カーネル法によるリッジ回帰は表現力が高いことが知られており、またその数学的背景の豊かさから多くの研究がなされてきました。 しかし、\(n\)個のデータ数に対して推論に\(\mathcal{O}(n^{3})\)の計算量が必要とされるため、計算量を低減させる方法を検討することは非常に重要です。 ここでは、Random Fourier Features 1と呼ばれる方法を紹介します。 実装も行ったがGistにも公開している。
AUTOはODE(常微分方程式)の分岐解析を扱うソフトウェアで、1980年に開発されて以来力学系界隈で使われてきました。 現在はGitHubにてコードが公開されて細々と(?)開発が続けられています。
AUTOは便利ではあるのですが、そのインストール方法がプログラム初心者には少し難しいことがあるそうなのでその流れを少しまとめてみました。 以下では基本的にMac OSでインストールする方法を述べますが、WindowsやLinuxでも同様だと思います。 また、最低限のターミナルでの操作は出来るものとしておきます。