アルゴリズムを変更してA5の部分群生成を15秒で完了した

部分群検定の代わりに部分群検定3(生成元により素群を生成する)を使うことで位数2×9, 位数3×8,位数4×6に変化した.位数3の部分群は4個なので多分重複が発生している.これを削減するかないし抑制しなくてはならない.⇒確かに{e,3,4}と{e,4,3}など順序が異なるだけの同一集合が4組ある.しかし,重複を排除しようとすると,■群S4は16個の部分群を持つ合成群である■位数2X7 位数3X4 位数4X3 飽和=0のように今度は不足してしまう.

見たところ重複が発生するのは位数2の場合に限定されているようにも思われる.しかし,そう断定するのは難しい.やはり,重複を検査するしかないのではないだろうか?とりあえず,ソートしないで直接比較するルーチンを作ってみよう.HasSameElementsという関数を作った.⇒これで以下のように変化した.■群S4は18個の部分群を持つ合成群である■位数2X9 位数3X4 位数4X3 飽和=0 位数4は実際には7個だが,この段階では検出できない.

最終出力は■群S4は28個の部分群を持つ■位数2X9 位数3X4 位数4X7 位数6X4 位数8X3 位数12X1のようになった.⇒一つ問題がある.部分群検定3で生成される素群は必ずしも排他的ではない可能性が出てきた.部分群検定5はすべての素群が排他的(単位元を除き直和)であることを仮定しているので,不整合が発生する可能性があるのではないか?S4の場合,1を含む素群は5個ある.{e,1,},{e,1,14,15,20,21,},{e,1,6,16,17,7,22,23,},{e,1,6,7,},{e,1,2,3,4,5,}

いや,これらの中で素群となるのは{e,1,}だけだ.素群は全部で16個あるが,これらの中には元が重複するものは存在していない.多分,素群にはノードの重複はないと言えるのではないかと思う.一応そういう仮定で進めることにしよう.いや,やはり重複はある.{e,7,}と{e,17,7,22,}では7が重複している.13も{e,10,23,13,}で重複し,16は{e,9,16,18,}で重複する.改訂版の動作をA5で確認してみよう.⇒素群は31個生成されているので,多分同じ動作になるだろう.ただし,現行論理では完了までに2時間掛かる!

A5の素群にはS4の場合と異なり,元の重複は存在していない.⇒重複があったとしても追加登録関数で弾いているので,実質的な障害にはならない.素群生成時にも追加登録関数は使われているので,ノードのダブりが生じる可能性はないとしてよい.これでいよいよ部分群検定の高速化に入れるのではないか?

一番分かりやすいのは素群SとS’から合成群SxS’を生成するという方法だろう.ただし,このとき不足するノードが発生するのでそれを注入する必要が生じる.これができれば多分相当高速なアルゴリズムになると思う.生成された素群数をsとすれば,現行の検定5では2^sのケースが発生するのに対し,s^2のコストでほぼ検定が完了するのではないかと思う.この再検定で生成された合成群に関してはさらに追検定が必要になる可能性はあるが,おそらくほとんどの場合は(なんらかの理由で)不用になるのではないかと思う.

位数最大となる極大な部分群の位数が分かれば,それだけでも計算コストは劇的に削減可能となるのだが… ⇒極大な部分群の最大位数を求める公式は得られていないので,最大部分群=12に固定して検定を実施したところ,20秒以内で完了した.確かに効果はある.

■群A5は57個の真部分群を持つ■位数2X15 位数3X10 位数4X5 位数5X6 位数6X10 位数10X6 位数12X5
経過時間=0:0:14.39

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA