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

1 次查看（过去 30 天）
Mathias
Mathias 2015-7-29
评论： 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
Matt J 2015-7-29
编辑：Matt J 2015-7-29
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
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...

请先登录，再进行评论。

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

回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by