疎行列計算、SuiteSparse for R

• 疎行列は大規模なデータで扱いたくなる
• SuiteSparseはこちら。MATLABを想定したCでの実装
• その実装についての本もある

Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms)

• 昨日のDECに関する記事でも疎行列を作ってその演算にSuiteSparseを使っていた(インストールがうまく行かなくて実行してはいないけれど)
• RのMatrixパッケージは"Classes and methods for dense and sparse matrices and operations on them using LAPACK and SuiteSparse."とのこと
  • 作成は"R Core Development Group"
  • 実際にはSuiteSparseのうちの"AMD, CHOLMOD, COLAMD, CSparse and SPQR from the SuiteSparse collection of Tim Davis"が実装されている、という
• Matrixパッケージの概要
  • BLAS (Basic Linear Algebra Subroutines)
  • Lapack (dense matrix)
  • TAUCS (sparse matrix)
  • UMFPACK (sparse matrix)
• Rでの線形代数ルーチンについて(Matrixパッケージ作成当時(2005年)の概説文書を眺めてみる)
  • Matrixパッケージの前の諸関数は、元々は%*%, qr, chol, solveは、Linpack(FORTRAN)
  • その後Lapack、BLASへの置き換えが進められた
  • Lapackは
    • 特別な形をした行列の処理を、その形を使って効率化する処理を実装、triangular matrices and symmetric matrices
    • QR decompositionsなどのDecomposisions処理で、分解結果を複数のオブジェクトの組として出力するようになった
    • ただし、Rでのその取り込みは、網羅的ではなく、backsolve, forwardsolve and chol2inv functionsは実装してあるが、それ以外は… 、とか、special structures (e.g. a QR structure)の実装にあたっては、Lapackのような「きちんとした形」ではなく、動くようには作ってあるが…形としては未完成(と言うことらしい)な実装だった
  • 疎行列対応はまったくしていなかった
  • 今回、密行列対応として、LapackとBLAS、疎行列対応としてTAUCS(Sparse Linear Solversパッケージ)とUMFPACK(これがSuiteSparseの作者が作った部分、これもSparse Linear Solvers、パイソンのscipyもこのUMFPACKには対応しているらしい)とMetisとをする
  • MetisはSuiteSparseを使うときにも入れさせられるそれ(こちら)で、"Serial Graph Partitioning and Fill-reducing Matrix Ordering"のパッケージ
• さらにMatrixパッケージの"2nd Introduction to the Matrix package(2006年)"にて、追加仕様を確認する
  • SuiteSparseのCHOLMOD (supernodal Cholesky),CSparse (a concise sparse Cholesky factorization package) and other parts (AMD, COLAMD:Ordering methods)が加えられたらしい