私は、整数SLUを高速化するためのコンテストに参加することを提案します。 アマチュア競技会と賞品は期待されていないことをすぐに警告したいので、この競技会が面白いと思う人やこれに自由な時間がある人を招待します。 このような問題を非常に効果的に解決できる人はほとんどいないという観点から、競争は有用かもしれません。
私はスポーツ番組のアマチュア競技を続けています。 多くの人が前の競争を気に入っており、次の競争は並列計算になると約束しましたが、技術的な理由から、私はそのような競争を無期限に延期しなければなりません。
1年前、私は行列に速度を掛けるタスクを提案しました。 結果は非常に興味深いものです。100倍以上の加速を達成しました。 今、線形代数の別の問題が提案されています-線形方程式Ax = bの整数システムの解。
行列Aとベクトルbは、符号付きの32ビットに収まる整数（-2 31〜2 31 -1）で構成されます。 この問題に対する答えは、有理ベクトルxです。 答えの分子と分母は非常に長くなる可能性があるため、長い算術のライブラリを使用することは禁じられていません 。
システムの最大次元はn = 200が提案されています。 ただし、参加者の1人が速すぎるプログラムを作成すると、この制限が大きくなります。 事実、「額」と書かれた通常の整数のガウス法は、ランダム行列にこのような制限があり、約10分間機能します。 もちろん、それはより速く書くことができます。
興味のある方は、コンテストの詳細をお読みください。
残念ながら、私は単独でコンテストを開催し続けているため、参加者に深刻な制限が生じます。 Windows 7（32ビット）でのみプログラムをテストする機会があるので、実行中のマシンでコンパイルされるEXEファイルまたはCPPソースを送信できます（この場合、MPIRライブラリのみが利用可能です）。 コンテストを実施する他の方法はありません。 ただし、参加者の行列の乗算の競合に対する同様の制限は停止しませんでした。
競争の良い結果は、5〜10秒で収まる実装です。
なぜこれが必要なのですか？
整数システムの正確な解法に関する情報を検索する過程で、この問題を解決できる人はほとんどいないことがわかりました。 私自身はこの分野の専門家ではありませんが、私の研究では整数SLUを思い付きました。これは非常に迅速に解決する必要があります。 この競争は、整数システムを解く速度で達成できる成功と、この場合の一般的な期待を理解するのに役立ちます。 競争の勝者は、計算線形代数の分野で働いている人々にとって非常に役立つ別の記事を書くことによって彼の経験を共有することができました。 Runetでそのような記事を見つけることはできなかったため、このギャップを埋めることが提案されています。
（コンテスト終了後）私の方法が参加者の方法よりも速いことが判明した場合、私はそのような記事を自分で書きます。 コンテストの終わりまで、私はそれに干渉しません。
もちろん、私は自分自身のために純粋に個人的な利益を探しているわけではなく、他人のコードを盗んで自分の目的に使用するつもりもありません。 私がコンテストを行っているのはこれが初めてではなく、誰もまだ文句を言っていないようです。 したがって、これに関するコンポーネントは複雑ではないかもしれません:)
頑張って