Haskellで行列式を計算する

アドべンヌカレンヌー

この記事は

PMOB Advent Calendar 2016 - Adventarの21日目の記事です。

• 前の記事[Not Found]

• 次の記事[みせられないよ]

プログラムコード

まぁ前々回のブログでも書きましたけど、

今読んでる「関数プログラミング珠玉のアルゴリズムデザイン」って本の内容そのままです。

これです。

Amazon CAPTCHA

この行列式演算のアルゴリズムは、Chioのピボット濃縮アルゴリズムである。

Chió Pivotal Condensation -- from Wolfram MathWorld

ここみて。

Chioのピボット濃縮アルゴリズムだが、これは比較的速い。

どれくらい速いかとか、何で速いか、とかは、は忘れた。

自分で調べろ。人に聞くな。

以下がコード。

condense = map (map det . pair . uncurry zip) . pair
            where pair (x:xs)       = map ((,) x) xs
                  det ((a,b),(c,d)) = a * d - b * c

det       :: [[Integer]] -> Integer
det [[x]] = x
det xss   =
  case break ((/= 0) . head) xss of
    (yss,[])     -> 0
    (yss,zs:zss) -> let x = det (condense (zs : yss ++ zss))
                        d = head zs ^ (length xss - 2)
                        y = x `div` d
                    in if even (length yss) then y else -y

cd k = map (map det . pair . uncurry zip) . pair
        where pair (x:xs)       = map ((,) x) xs
              det ((a,b),(c,d)) = (a * d - b * c) `div` k

det'         :: Integer -> [[Integer]] -> Integer
det' k [[x]] = x
det' k xss   =
  case break ((/= 0) . head) xss of
    (yss,[])     -> 0
    (yss,zs:zss) -> let x = det' (head zs) (cd k (zs : yss ++ zss))
                    in if even (length yss) then x else -x

暇だったら加筆します。

ではでは。