qr decomposition run-time performance

2020 8 31
2 个回答
更新时间：2020 9 1
9 次查看（30 天）

0 个投票

Hi,
I'm comparing the run-time of the "qr" function:
Option1: R = triu(qr(A))
Option2: [~, R]=qr(A) (or [Q, R]=qr(A)),
Only the "R" output is required.
I've tested them on a large number of possible choices of A, a full (not-sparse) matrix with m >> n.
The result was a significant run-time advantage for triu(qr(A)).
To the best of my knowlegde from Matlab documention, option1 use LAPACK xGEQRF Householder Reflectors, but I couldn't find how option2 was implemented.
Can anyone explain what is (or may be) the cause for such performance difference?
(Using Matlab R2019b)
Thank you in advance!

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

回答（2 个）

Bruno Luong
Bruno Luong 2020-8-31
编辑：Bruno Luong 2020-8-31

2 个投票

I'm pretty sure both Q-less-qr and qr use the same algorithm.
What you should try is
Option 3
[~, R] = qr(A,0);
that will return (n x n) R matrix without the bottom part padded with 0.
It's about 2 times slower than q-less qr, but it can be simply explained by Q (m x n) that is built and cleared.
If you do the Option2
[~, R] = qr(A);
the invisible cleared Q is (m x m), totally useless orthogonal much bigger matrix that has been built and then cleared.

4 个评论
显示 2更早的评论 隐藏 2更早的评论

Niv Shapira
Niv Shapira 2020-8-31
Thank you very much Bruno, i'm looking into it!
Niv Shapira
Niv Shapira 2020-8-31
Hi Bruno,
I've done a brief test for the three options (not sure it's done properly):
timeAcc = 0;
for ii = 10000:-1:1
A = magic(500);
A = A(:,1:7);
tStart = tic;
R = triu(qr(A));
timeAcc = timeAcc + toc(tStart);
disp(timeAcc/(10001-ii));
end
triuQR = timeAcc/10000;
clearvars A tStart R timeAcc
clc
timeAcc = 0;
for ii = 10000:-1:1
A = magic(500);
A = A(:,1:7);
tStart = tic;
[~,R] = qr(A);
timeAcc = timeAcc + toc(tStart);
disp(timeAcc/(10001-ii));
end
qrTime = timeAcc/10000;
clearvars A tStart R timeAcc
clc
timeAcc = 0;
for ii = 10000:-1:1
A = magic(500);
A = A(:,1:7);
tStart = tic;
[~,R] = qr(A,0);
timeAcc = timeAcc + toc(tStart);
disp(timeAcc/(10001-ii));
end
compactQR = timeAcc/10000;
The results were:
triuQR = 1.118231647999998e-04 [sec]
qrTime = 0.001107686688700 [sec]
compactQR = 2.532942389999996e-04 [sec]
Bruno Luong
Bruno Luong 2020-8-31
This timing results seem to be inline with what I have done earlier today.
Niv Shapira
Niv Shapira 2020-9-1
I'll add here a note to whom it may concern:
The test i've performed above on the "magic" matrix "A" was not sufficient. The qr functionality and run-time may vary dramatically depending on the input matrix properties. It seems that for some matrices the run-time difference between triu(qr(A)) to qr(A,0) (or qr(A)) might be even larger.

请先登录，再进行评论。

Christine Tobler
Christine Tobler 2020-9-1

2 个投票

When a "~" is used for a return value, this is only for code clarity. MATLAB still needs to compute that value, so the second case is computing the Q, even though you don't intend to use it.

类别

在 帮助中心 和 File Exchange 中查找有关 Mathematics 的更多信息

产品

版本

R2019b

标签

Community Treasure Hunt

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

Start Hunting!

Translated by