FFTW

が面白いらしい。Ocamlは読めないので、ふいんきだけ

スライド
http://jdj.mit.edu/~stevenj/fftw-18.337.pdf

論文(短い)
A Fast Fourier Transform Compiler

論文(何か長い。ので、読んでない)
The Advanced FFT Program Generator GENFFT


FFTWでFFTを行う時には、plannerが、入力データサイズとかに応じて最適なアルゴリズムを自動的に求める。このアルゴリズムは、codeletと呼ばれるコードを組み合わせることによって作られる。んで、このcodelet部分が、FFTWのソースの80%だか95%だかを占めてて、Ocamlで記述したgenfftによって、自動生成されたものらしい


genfftは
・入力データサイズに応じて、算術演算と変数と"ポインタ"だけがある(生成されたCのコード見ると、if文やループすらないっぽい。その分最適化が簡単になるのかもしれないが)ミニ言語のようなもの(dag=directed acyclic graphで表現される)で書いたナイーブなコードを生成

・そうして出来たコードに、適当に算術式の簡約(定数畳み込みとか、共通部分式の除去とか、0*x=0,0+x=xみたいな簡約)を施す。この時、memoiseを使う。memoiseは最初は普通に副作用を利用して書いてたけど、それだとバグが発見しづらいとか、なんかそういう理由で、State Monadを使ったMonadic Styleで書くようにしたとか、そういう話。まあ、これは別にどってことない

・最後に、レジスタ割り当てやキャッシュ最適化を考慮しつつ、dagのtopological sortを行って、実行順序を決定する。これは、machine-independentに行うらしい(よく分からんかった)

という手順を踏んで得た抽象表現を機械的にCに落として、codeletを得る。んで、こうやって自動生成されたコードは、人間ががんばって書くよりも効率いいコードを生むことがあるとかなんとか。でもって、最適化に関する部分は、全部dag表現の段階で行われてるので、C以外の言語のコードを生成することも可能(まあ普通はCでいいと思うけど、GPGPU用の専用言語が開発されてたりするようなので、そういうのにも即対応できたりする可能性を秘めてていいんでないかな、と)。全体としては、特に難しいステップはないと思う


simplificationやschedulingの大体の部分は、FFT-independentに行われる。なので、genfftは、fft以外にも応用できたりしないかなー、ということを思った。まあ、genfftはかなりFFTの特殊事情に依存してて、それで簡単かつうまくいってる気もするけど、それでもHaskellみたいな高級言語の場合、Haskellで直接高速な数値計算アルゴリズムを実装するより、高速なCコードを生成する方が簡単だったりするかもしれない。

■

A Functional Correspondence between Evaluators and Abstract Machines
を読んだ。


とりあえず、
・MLが読めない(こともないけど、読みづらい)
・ていうか、closure conversionってなんだっけ？
・Kirivine's machineとかCEK machineとか初めて聞いた
・ていうか、source languageが簡単すぎるだろ(ただのラムダ計算のようだ)


話としては、なんかevaluatorにclosure conversion施して、CPS変換して、defunctionalizationしたら、abstract machineが得られるとか、あるいは逆のプロセスを経れば、abstract machineと対応するevaluatorが出るとか、そういう話らしい。なんか騙された感がするというか、えらい簡単だな。closureほげほげとか、CPSほげほげとかって、コンパイラの標準的なプロセス(いやまあ、最近はCPS変換とかはしないかもしれんけど)で、evaluatorを「コンパイル」したら、抽象機械ってことなのか。なんかよくわからんなー

共形場理論

共形場理論(正確には、二次元有理共形場理論)が面白い今日この頃。
Vertex Algebras and Algebraic Curves
を読んだ。


素朴には、共形場理論は、共形変換で不変な場の理論ということらしいが、よくわからん。
・central charge=0のVirasoro代数は、複素平面上の無限小共形変換にはなってなくて、複素平面から原点を除いた領域上の無限小共形変換になってる。原点で特異性を持つことを許す物理的な理由が謎

・複素平面から原点を除いた領域上の無限小共形変換のなす代数ではなくて、その中心拡大(=Virasoro代数)を考える物理的な理由が謎

・Virasoro代数対称性(あるいは、アフィン・リー代数対称性とかでも)を持つってのは、ハミルトニアンと可換なオペレータの全体がVirasoro代数(orアフィン・リー代数)をなすって理解でいいんだろうか。しかし、そういうハミルトニアンがexplicitに与えられてるのを見たことがない。ハミルトニアンなしでも、対称性のみで全ての量が計算できるってのがウリなのかもしれんけど


まあ、どっちみち物理の素養はあまりないので、そのへんはよいとして、数学的には、二次元有理共形場理論=有理頂点作用素代数の理論、という理解でよいらしい。頂点作用素代数自体は、いかにも技巧的で人工的な感じのする対象なので、なんかもっといい定式化があるだろうとは思うけど。有理頂点作用素代数の加群の圏は、modular tensor categoryになる(が、逆は言えないので、うまく有理頂点作用素代数の加群の圏というのを特徴付けられるといいんだけど)。

で、表現論的説明は明快でよいのだけど、一方で、(WZW模型の場合)conformal blockの幾何学的な定義(の一つ?後半話が追えてない)として、リーマン面上の平坦G-主束のモジュライ空間上のあるampleな直線束の切断の空間というのがあって、そういうのと表現論的共形場理論がどういう風に結びつくか(私の中で)謎だった。しかし、それを書くには、私の代数幾何学の素養が足りない(足りないことばっかだな。要するに、あんましきちんと理解できなかった)。まあ、今のところ、代数的にうまくいくのは、種数0の場合と、精々1の場合までで、種数2以上のケースもうまく代数的に捉えられるといいな〜とか。