行列の積分解

行列のリスケーリングは、効果的でした。そこで、これを前述のSpMV実装に適用したいのですが、一つ問題がありました。

\begin{align}(ABC)^{ \mathrm{ t } }=C^{ \mathrm{ t } }B^{ \mathrm{ t } }A^{ \mathrm{ t } } \end{align}

A,Cは、スケーリングの為の対角行列なので

\begin{align}(ABC)^{ \mathrm{ t } }=CB^{ \mathrm{ t } }A \end{align}

行列の積の結合法則により、

\begin{align}(ABC)^{ \mathrm{ t } }=C(B^{ \mathrm{ t } }A) \end{align}

\begin{align}\begin{pmatrix}y\end{pmatrix}=(ABC)^{ \mathrm{ t } }\begin{pmatrix}x\end{pmatrix}=C(B^{ \mathrm{ t } })\begin{pmatrix}Ax\end{pmatrix}\end{align}

と計算することが出来ます。ナーススケジューリングの場合、Bの殆どの係数は１です。そのままスケーリングしてしまうと、SpMVの積和演算をそのまま実行する必要がありますが、(3）のように計算すれば、その殆どを加算として計算できます。昨今のAVX2では、積和演算命令があり、加算のLatencyと変わらないし、むしろ積を分解することにより積回数は、増えてしまいます。その意味では得する部分はありません。しかし、行列の積係数をメモリしないでよいというアドバンテージが巨大インスタンスについては効いてくるはずです。