論文の概要: Fast multiplication by two's complement addition of numbers represented
as a set of polynomial radix 2 indexes, stored as an integer list for
massively parallel computation
- arxiv url: http://arxiv.org/abs/2311.09922v1
- Date: Thu, 16 Nov 2023 14:21:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-17 13:52:21.657495
- Title: Fast multiplication by two's complement addition of numbers represented
as a set of polynomial radix 2 indexes, stored as an integer list for
massively parallel computation
- Title（参考訳）: 超並列計算のための整数リストとして格納された多項式半径2指数の集合として表される2の補数加算による高速乗算
- Authors: Mark Stocks
- Abstract要約: Polynomial integer index multiplication' は、ピソン符号で実装されたアルゴリズムの集合である。
本研究では,Number Theoretic Transform (NTT) とKaratsuba より高速な乗算法を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We demonstrate a multiplication method based on numbers represented as set of
polynomial radix 2 indices stored as an integer list. The 'polynomial integer
index multiplication' method is a set of algorithms implemented in python code.
We demonstrate the method to be faster than both the Number Theoretic Transform
(NTT) and Karatsuba for multiplication within a certain bit range. Also
implemented in python code for comparison purposes with the polynomial radix 2
integer method. We demonstrate that it is possible to express any integer or
real number as a list of integer indices, representing a finite series in base
two. The finite series of integer index representation of a number can then be
stored and distributed across multiple CPUs / GPUs. We show that operations of
addition and multiplication can be applied as two's complement additions
operating on the index integer representations and can be fully distributed
across a given CPU / GPU architecture. We demonstrate fully distributed
arithmetic operations such that the 'polynomial integer index multiplication'
method overcomes the current limitation of parallel multiplication methods. Ie,
the need to share common core memory and common disk for the calculation of
results and intermediate results.
- Abstract（参考訳）: 整数リストとして格納された多項式ラディクス2指標の集合として表される数に基づく乗法を示す。
Polynomial integer index multiplication' は、ピソン符号で実装されたアルゴリズムの集合である。
本手法は,数論的変換(ntt)とカラツバ(karatsuba)のどちらよりも高速に乗算できることを示す。
多項式 radix 2 整数法との比較目的で python コードにも実装されている。
任意の整数または実数を整数のインデックスのリストとして表現することができ、基数 2 の有限級数を表す。
数値の整数インデックス表現の有限列は、複数のCPU/GPU間で保存および分散することができる。
加算と乗算の演算はインデックス整数表現で動作する2の補足加算として適用でき、与えられたcpu/gpuアーキテクチャに完全に分散できることを示す。
本研究では,'多項整数インデックス乗算'法が並列乗算法の現在の限界を克服するような完全分散演算を実証する。
すなわち、結果の計算と中間結果の計算に共通コアメモリと共通ディスクを共有する必要がある。
関連論文リスト
- An average case efficient algorithm for solving two variable linear diophantine equations [0.0]
2つの可変線形ディオファンチン方程式を解くことは、RSAや楕円曲線暗号などの多くの暗号プロトコルに応用できる。
2つの線形ディオファンチン方程式を解くために2つのアルゴリズムを再検討する。
論文 参考訳（メタデータ） (2024-09-21T07:51:12Z) - Low-Complexity Integer Divider Architecture for Homomorphic Encryption [5.857929080874288]
ホモモルフィック暗号化(HE)は、計算を直接暗号文で行うことができ、プライバシ保護のクラウドコンピューティングを可能にする。
余剰かつ活発な数学的証明を計算するアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2024-01-19T23:53:59Z) - CoLA: Exploiting Compositional Structure for Automatic and Efficient
Numerical Linear Algebra [62.37017125812101]
機械学習における大規模線形代数問題に対して, CoLA という, 単純だが汎用的なフレームワークを提案する。
線形演算子抽象と合成ディスパッチルールを組み合わせることで、CoLAはメモリと実行時の効率的な数値アルゴリズムを自動的に構築する。
偏微分方程式,ガウス過程,同変モデル構築,教師なし学習など,幅広い応用で有効性を示す。
論文 参考訳（メタデータ） (2023-09-06T14:59:38Z) - Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。
本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。
大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
論文 参考訳（メタデータ） (2023-09-01T18:02:04Z) - Scaling Integer Arithmetic in Probabilistic Programs [21.26857534769979]
本稿では、整数演算のリッチな論理構造を利用する離散分布のバイナリ符号化戦略を提案する。
このアプローチは算術演算ではるかに大きな整数分布にスケールできることが示される。
論文 参考訳（メタデータ） (2023-07-25T22:21:07Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - An Efficient Summation Algorithm for the Accuracy, Convergence and
Reproducibility of Parallel Numerical Methods [0.0]
我々は浮動小数点数の列をまとめる新しい並列アルゴリズムを導入した。
プロセッサ数で簡単にスケールアップできるこのアルゴリズムは、まず同じ指数の数を加算する。
この記事では、いくつかの特性に関して、その効率を広範囲に分析する。
論文 参考訳（メタデータ） (2022-05-11T08:31:48Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
量子コンピューティングの大きな約束の1つは、重ね合わせ現象を用いたSIMD(単一命令 - 複数のデータ)演算の実現である。
我々は、符号なし整数量子回路を便利に生成できる半ブールと呼ばれる符号化形式を導入している。
我々は、このタイプの評価を、アンシラのないインプレース乗算や整数係数評価などの追加機能で拡張する。
論文 参考訳（メタデータ） (2021-12-20T14:00:36Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。