Cholesky vs Eigs speed comparison?

69 次查看（过去 30 天）
Lennart Sinjorgo
Lennart Sinjorgo 2024-10-25，15:05
编辑： Bruno Luong 2024-10-29，9:50
I have many large (8000 x 8000) sparse PSD matrices for which I would like to verify that their largest eigenvalue is at most some constant C. If A denotes such a matrix, there are two ways to check this.
  1. eigs(A,1) <= C
  2. chol(C*speye(size(A,1)) - A) (and inspect the output flag)
Somehow, method 1 is much faster than 2 (this difference is not due to the computation time of C*speye(size(A,1)) - A) . Why is that? The general consensus is that cholesky decomposition is the fastest way of determining PSD-ness of matrices. Is chol not as fast for sparse matrices as eigs?

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

回答（1 个）

Bruno Luong
Bruno Luong 2024-10-25，16:03
编辑：Bruno Luong 2024-10-28，14:07
Your test of PSD is not right. You should do:
eigs(A,1, 'smallestreal') > smallpositivenumber % 'sr', 'sa' for older MATLAB
EIGS compute one eigen value by iterative method. It converges rapidly for
eigs(A,1)
  6 个评论
显示 4更早的评论
Bruno Luong
Bruno Luong 2024-10-28，19:12
编辑：Bruno Luong 2024-10-28，22:38
Ran in:
An example with sparse matrix based on Haar basis. The ratio of two matrix norms increases like sqrt(N)
N = 2^14
N = 16384
A = haar(N);
% eigs(A,1) must be 1
norm(A,inf) / eigs(A,1)
ans = 128.0000
function S=haar(N)
if (N<2 || (log2(N)-floor(log2(N)))~=0)
error('The input argument should be of form 2^k');
end
p=[0 0];
q=[0 1];
n=nextpow2(N);
for i=1:n-1
p=[p i*ones(1,2^i)];
t=1:(2^i);
q=[q t];
end
j = 1:N;
I = 1+0*j;
J = j;
V = 1+0*j;
for i=2:N
P=p(1,i); Q=q(1,i);
j = 1+N*(Q-1)/(2^P):N*(Q-0.5)/(2^P);
I = [I, i+0*j];
J = [J, j];
V = [V, 2^(P/2)+0*j];
j = 1+(N*((Q-0.5)/(2^P))):N*(Q/(2^P));
I = [I, i+0*j];
J = [J, j];
V = [V, -(2^(P/2))+0*j];
end
S = sparse(I,J,V,N,N);
S=S/sqrt(N);
end
Bruno Luong
Bruno Luong 2024-10-29，9:31
编辑：Bruno Luong 2024-10-29，9:50
Ran in:
Here is an example where the ratio is huge (= N), discovered by codinng mistake .;)
N = 2^16
N = 65536
j = 1:N;
I = 1+0*j;
J = j;
V = 1+0*j;
A = sparse(I,J,V,N,N);
norm(A,inf) / eigs(A,1)
ans = 6.5536e+04

请先登录，再进行评论。

类别

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

标签

产品


版本

R2022a

Community Treasure Hunt

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

Start Hunting!

Translated by