行列の要素が0 or 1であり、加法がbit or、乗法がbit andであるような束（加法がxorではないので、ブール環にはなっていません。また、束であることは特に使いません）上での行列積演算を考えます。
これが疎行列、つまり行列の成分がほとんど零であり、非零な要素が個くらいしかないような行列でありれば、適当な圧縮表現上で取り扱うことで計算量は
となります。
密行列であっても、N ≦256であれば、AVX2のvptest命令（二つのymmレジスタに乗っかっている256bit整数のbitwise andを取り、その結果が0であるかが分かる命令）を使えば、になります（
Nが有限である時に漸近記法を用いるのは厳密にはおかしいですが、記号の濫用ということでお許しください）。以下、N ≦256の場合のことを考えます。
N = 256の時、一つの行列を保持するのに必要なメモリは8KiBであり、三つの行列を保持しても24KiBであるため、L1キャッシュのサイズが32KiBであれば全ての情報が収まります。
その場合、行列積を速くする種々のテクニックを使う必要はあまりありません。
普通の二重ループ（最内ループはvptest命令一つになるので三重ループにはなりません）を書けば十分です。
行列のべき乗を計算する場合、もともとの行列が疎行列であってもべき乗を繰り返すうちに密行列になって行ってしまうので、どこかで手法を切り替える必要があります。
疎行列の手法と密行列の手法を切り替えるべき境界について調べたところ、行列の非零成分の数が、個くらいのところだということが分かりました。
つまり、行列の非零成分の数が
個よりも少なければ疎行列の手法を使った方が高速であり、それよりも多ければ密行列の手法を使った方が高速であるということです。
疎行列の手法の場合、演算結果が零になるようなビットにはアクセスしないのが高速化につながります。この効果は行列が疎である（非零な成分が少ない）ほど高まります。
一方、非零な要素の数がを超える場合、計算量は
に収まらないため、非零な要素の数が増えるにしたがって、非零な要素の数によらない密行列の手法が相対的に高速化します。
