行列積計算を高速化してみる｜やまもと
機種名 ：MacBook Pro CPU ：Dual-Core Intel Core i5 動作周波数 ：2.9GHz プロセッサ数：１ コア数 ：２ SMT ：有効 L1キャッシュ：32KB L2キャッシュ：コアあたり256KB L3キャッシュ：４MB明示されていませんが、購入時期から考えて、CPUのマイクロアーキテクチャはSkylake Microarchitecture（最新資料だと、Skylake Client Microarchitecture）だと思われます。 動作周波数は、CPUIDの情報だと基本が2.9GHz、最大が3.3GHzに設定されていました。CPU使用量が増加すると、Tarbo Boost テクノロジーによって、自動的に動作周波数が上がる可能性があります。 コア数は2個ありますが、まずは１コア性能を向上させたいと思います。SMT（ハイパー・スレッ
カハンの加算アルゴリズム - Wikipedia
カハンの加算アルゴリズム（英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合[1]に、計算の途中の誤差を保持することで補正する。Compensated summation（補正加算）とも呼ぶ[2]。 単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）[3]。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる[3]。 このアルゴリズムの名は考案し
ubuntu 14.04でBLASを使う
ubuntu 14.04上でBLASをパッケージで入れて使ってみたのでメモを残しておきます。 BLASは、Basic Linear Algebra Subprogramsの略で、行列積などの基本的な行列計算のためのライブラリです。LAPACKなどの様々なプログラムから呼び出されます。行列計算は環境によって最適な書き方が違うので、行列計算の部分を差し替え可能なように分離しておきユーザが最適なBLASに差し替えて最高の性能を出す、ということを意図しています。 多くの環境で、デフォルトのBLASは単なるfor文で書かれたちっとも速くない「reference BLAS」と呼ばれるものになっています。自分の環境でも、reference BLASが入っていました。この場合例えばnumpyの行列計算は、全くCPU本来の性能を出せていません。 ubuntu 14.04では、atlasとopenblasとい
いまどきのmatmul
概要 経緯 : http://d.hatena.ne.jp/w_o/20141021#1413893835 Host 1700msec、Epiphany 170msecとかになって、さすが、16coreだから10倍速いみたいな話になったが、 経験的に、こういうのってナイーブCと比較してるから、普通にマルチスレッド & NEON使えば、10倍差ぐらいすぐはやくなんじゃね？ と、思ってNEON + スレッド化matmulを探したのだけど、見当たらなくて、探すより書いたほうがはやそうだったので書いた。 というのがあって、今更matmulを実装したのでその話について書く。 1ノード Haswell 正方行列 単精度 サイズは128の倍数だとか制限付けてもよい という条件でどうやって効率上げていくかについて説明する。 今日の結果は N = 2000〜3000 で効率 80% ぐらい。 まあ多分もっと
kv - a C++ Library for Verified Numerical Computation
1. はじめに 本ページでは、精度保証付き数値計算を行うためにC++で作成した ライブラリ群を公開している。 特に非線形計算の精度保証を行うとき、template機能によって 複雑な数値型をすっきり記述でき、なおかつ "zero-overhead principle" で 計算速度が遅くならないC++は、非常に適していると言える (ほぼ唯一無二であると作者は考えている。)。 精度保証付き数値計算とkvライブラリの概要については、 このスライドを見て欲しい。 kv-intro.pdf (全84ページ) 2007年秋頃～2013年春頃の間は、区間演算を行うのにboostに含まれている intervalライブラリを用いて開発していたが、 boost.intervalは残念ながら不完全な部分が多く ライブラリ本体に手を入れざるを得なかった。 boost全体がアップデートする度にinterval部分
数値計算 - Microsoft Cloud Numerics の数学関数をテストする
図 2 の例から導き出せる結論は、少数の ULP の範囲内で正確なアルゴリズムを使用して特別な関数が実装されることです。図 2 で示される最悪の場合は、誤差が 6 ULP 以下で、これは数値の最低数位の小数点以下 log10(2^6) = 1.8 桁と一致します。倍精度浮動小数では、これは 1.3323e-015 の相対誤差に相当します。 最先端のテスト ここまでで、厳密なテスト手法を Microsoft Cloud Numerics 数学パッケージで使用されるアルゴリズムの検証にうまく適用できました。関数の条件数から導き出したテストの許容誤差を使用することで、誤差が関数の戻り値の最後の数桁でのみ発生している場合でも、不正確な関数の実装を特定して修正できるようになります。テストの許容誤差を固定すると、故意の誤り (関数の特異点の近接など) を引き起こさない厳密なテストを提供できません。テス
ÉâÆ°¾®¿ôÅÀ±é»»¤Ë¤Ä¤¤¤Æ
ÉÕÏ¿ D ÉâÆ°¾®¿ôÅÀ±é»»¤Ë¤Ä¤¤¤Æ Ãí - ¤³¤ÎÉÕÏ¿¤Ï¡¢1991 ǯ 3 ·îȯ¹Ô¤Î "Computing Surveys" ¤Ë·ÇºÜ¤µ¤ì¤¿ "Every Computer Scientist Should Know About Floating-Point Arithmetic" ¹Æ (David GoldbergÃø) ¤òºÆÊÔ½¸¤·¡¢Ãøºî¸¢¤òͤ¹¤ë Association for Computing Machinery ¼Ò (Copyright 1991) ¤Îµö²Ä¤Î¤â¤È¤Ë¡¢°õºþ¤·¤Ê¤ª¤·¤¿¤â¤Î¤Ç¤¹¡£ ³µÍ× ÉâÆ°¾®¿ôÅÀ±é»»¤Ï¡¢³µ¤·¤ÆÆñ²ò¤ÊÌäÂê¤È¤·¤Æ¼õ¤±¼è¤é¤ì¤ë¤³¤È¤¬¤¢¤ê¤Þ¤¹¡£¥³¥ó¥Ô¥å¡¼¥
Square root of a matrix - Wikipedia
In mathematics, the square root of a matrix extends the notion of square root from numbers to matrices. A matrix B is said to be a square root of A if the matrix product BB is equal to A.[1] Some authors use the name square root or the notation A1/2 only for the specific case when A is positive semidefinite, to denote the unique matrix B that is positive semidefinite and such that BB = BTB = A (fo
Numerical Computation as Software
Numerical Computation as Software ソフトウェアとしての数値計算 Last Update: 2007-10-21 お断り＆言い訳 [2007-10-21] 「今後の当面の方針」について [2007-10-13] Version 1.0.3.2公開。 内容 [Bug] 表紙 目次 初めに 数値計算のための予備知識 数学ソフトウェアの現状と数値計算の役割について 数の体系，コンピュータ，浮動小数点数 浮動小数点数と丸め誤差 多倍長計算 計算量について 初等関数の計算 連立一次方程式の解法1-- 直接法 ノルム，条件数，連立一次方程式の誤差解析 連立一次方程式の解法2 -- 反復法 連立一次方程式の解法3 -- Krylov部分空間法 行列の固有値・固有ベクトル計算 非線型方程式の解法 代数方程式の解法 補間と最小二乗法 数値微分と数値積分 常微分方程式の初期値問
Boost.uBLAS の遅延評価について - yanoの日記
今回は uBLAS の遅延評価について説明します． uBLAS が他の数ある行列演算ライブラリと比べもっとも性質を異にしているものがこの遅延評価です． これは uBLAS 最大の特徴であり，Expression template という技法により実現されています． その実装はとても複雑ですが，実際に uBLAS を利用するユーザはそのことを意識しなくてもよい作りになっています． Expression template については以下が詳しいです． Expression Template しかし効率的なプログラムを書くという点で，この uBLAS の遅延評価について知っておくことは決して損にはならないでしょう． さて，次のようなコードを考えます． matrix A, B; prod(A, B); 何が起きるでしょうか？普通のライブラリなら prod 内で行列 A と行列 B の乗算が行われ，
浮動小数点数の比較
浮動小数点数の比較アルゴリズム ホーム イントロダクション 許容値の選び方 close_at_toleranceアルゴリズム 編集 謝辞 参考 イントロダクション とても大きな数値は小さな数値では、abs(f1-f2) <= eというシンプルな解放では浮動小数点数の 等値チェックはうまくいかないことがある。そのため、operator=(...)の使用はふさわしくないと言える。 この浮動小数点数比較アルゴリズムはより信頼性の高い、Knuthの[1]の文献で紹介されている方法を元にしている。 不動小数点数 u と v 、許容値 e が与えられたとする。
FLP35-C. 浮動小数点数値を比較する際には精度を考慮する
FLP35-C. 浮動小数点数値を比較する際には精度を考慮する C の浮動小数点演算は正確ではない。特に、浮動小数点数を比較する際は、可搬性があり計算結果が同じになる方法で行う必要がある。 違反コード c と a / b の比較の結果は、あらかじめ予測することはできず、実行するマシンやコンパイラ、最適化レベルの違いによって変わる可能性がある。 float a = 3.0; float b = 7.0; float c = a / b; if (c == a / b) { printf("Comparison succeeds\n"); } else { printf("Unexpected result\n"); } 処理系固有の詳細 このコードを、IA-32 Linux 上の GCC 3.4.4 で最適化レベル 1 以上、あるいは IA-32 Windows XP 上の Microsof
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Charming Python: Functional programming in Python, Part 3
数値計算ガイド