0

私はスパース行列の使用に慣れていませんが、スペースを節約するために、スパース行列を使用する必要があります。私は次のマトリックスを理解しています：

10   0    0    0   -2    0
3    9    0    0    0    3
0    7    8    7    0    0
3    0    8    7    5    0
0    8    0    9    9    13
0    4    0    0    2   -1

次のような3つのベクトルで表すことができます。

[10 -2 3 9 3 7 8 7 3 8 7 5 8 9 9 13 3 2 -1] // nonzero_vals

[1 5 1 2 6 2 3 4 1 3 4 5 2 4 5 6 2 5 6] // col_indices

[1 3 6 9 13 17 20] // row_ptr (indices of values that start row)

私の問題は、O（1）時間での値ルックアップの適切な方程式を決定することです。たとえば、場所（2,2）に格納されている行列値を返したい場合、9を返すにはどうすればよいですか？また、ルックアップ座標がスパース行列で表されていない場合、O（1）時間でも、0を返すにはどうすればよいですか？

私はあなたが提供できるどんな助けにも感謝します。これには十分に確立された方程式があると確信していますが、それらを見つけることができません。

4

1 に答える 1

2

任意の（i、j）座標で値を取得するためのO（1）手順はありません（少なくとも前処理なしでは）。あなたができる最善のことは、列インデックスの二分探索手順を介して、平均してO（log N）（行列はMxN ）です。*

*ええと、実際にはO（log k）です。ここで、kは行内の非ゼロの数です。ただし、密度が行列のサイズとは無関係であると仮定した場合（これはよくあることです）、O（log N）は有効です。

于 2013-03-18T22:30:21.923 に答える