2011-09-16 31 views
1

私はコンピュータグラフィックスのクラッシュコースを取っていますが、私たちは2D変換をカバーしており、インストラクターはそのマトリックスの逆数を計算するのは計算量が多い(直交行列の転置も逆行列であるため)計算上有用である。時間の制約とクラスの性質のために、彼はなぜこれがあるのか​​について詳しくは触れておらず、誰かがそうすることができるのだろうかと思っていました。行列を転置する計算量と逆算する計算量

私は特に、各プロセスに関連するCPU/GPU命令の違いに気づいています。あるいは、間違っていると、ボトルネックが発生しているスタックの最低レベルになります。私はまた、あらゆる種類の資源、書籍、ウェブサイトなどを学ぶことに興味があります。ここで、こうした種類の問題やボトルネックについてもっと学ぶことができます。

答えて

2

は、最悪の場合、O(N 2 )動作です。それはこれらのことをするコストです。

ほとんどのアプリケーションは、逆行列を見つけず、線形システムAx = bを解くために行列逆行列を計算しません。分解と三角形解法を使用してこの問題を解く方がより高速で正確です(例えば一般的な非特異行列の場合はLU decompositionを参照してください)。行列の逆数は、Gauss-Jordan elimination(および他の手法)を使用して計算することができます。

利用可能なルーチンについては、LU分解(おそらく行列逆行列)の計算に使用できるLAPACK実装を見つけることができます。

1

行列転置は、単に行列の要素のスワップを含みます。つまり、単なるデータの移動であり、計算はありません。 逆行列 OTOHは、かなりの計算量を必要とします。一般的な非特異N×nの行列の逆行列を計算することは、O(N )操作であるのに対し、N×nの行列を転置

関連する問題