Get linearly depend rows of matrix 2N x N with N large (GPU-compatible)

2 次查看（过去 30 天）

Mathias 2015-7-29

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/231628-get-linearly-depend-rows-of-matrix-2n-x-n-with-n-large-gpu-compatible

评论： Mathias 2015-7-30

Hello everyone,

I know that there is already a lot of helpful information on this topic here: I am having a N x 2N matrix A and would like to remove these columns of A such that A has full rank and is optimally conditioned. This works amazingly well with the QR decomposition with column pivoting, as can be used in Matlab as follows:

N       = 1000;
A       = rand( N, 2*N );
[Q,R,E] = qr(A,'vector');
tol     = 1.0;
rankA    = find( abs(diag(R)) >= tol, 1, 'last');
idx    = sort(E(1:rankA));
A_red   = A(:,idx);

The problem, however, is that N will get quite large, something like N = 10000. The GPU version of the QR algorithm is very fast, but it does not support the column pivoting (only Q and R are returned, not the permutation vector E). Do some of you know about ways to use different fast approaches (SVD, EIG, ...) to solve the above problem? Or maybe there is a way to synthesize some permutation vector E from the Q and R matrices? Otherwise, are there GPU implementations with column pivoting available which can be easily compiled to be used in Matlab? Thanks a lot in advance for your helpful comments!

Warm regards

Mathias

2 个评论
显示无隐藏无

Matt J 2015-7-29

编辑：Matt J 2015-7-29

在 MATLAB Online 中打开

I wonder even about the QR method. I can see that this would work as long as R always satisfies

abs(R(i,i))>=abs(R(i,j))

for all j>=i. This property always seems to hold in randomized examples. Can't seem to find a proof of this, however.

Mathias 2015-7-30

Hey, I am not quite sure if I understand you correctly? You mean you're wondering if the method I've shown works in any case? It wouldn't be too critical if the resulting reduced matrix was not be the strictly optimal solution. I am more interested in the pattern, in which the rows are removed from the matrix.

That's why I could imagine, that you could actually use another "metric" for how important the rows are rather than the pivoting order...

请先登录，再进行评论。

请先登录，再回答此问题。