一些关于随机矩阵的算法
共 4374字,需浏览 9分钟
·
2022-07-30 16:46
来源:PaperWeekly 本文约1500字,建议阅读5分钟 本文简单介绍有关于 random matrix 的算法。
本文介绍一下我硕士论文中用到的关于随机矩阵 GUE 的算法,真的超级好使,谁用谁知道!关于 GUE 的简单介绍,可以看下:
function GUE = GUE_matrix_MC_create_GUE(size,seed)
%set random seed
rng(seed);
tempMat=randn(size)+1i*randn(size);
GUE=(tempMat+tempMat')/2;
end
对存储的要求非常大,也就是 。比如说我们需要大概 80G 去存储一个 1w 乘 1w 的矩阵。 构造出来的是一个 dense 的矩阵,也就是大多数分量都不是零!那当我们要去算 的时候,我们基本只能使用最基本的算特征值的方法,复杂度就是 !
他对存储的要求比较低。
他有点特殊,可以用一些算法复杂度比较低的方法来算他最大的特征值。
他最大的特征值的分布是等于 的分布的。
和 随机变量都是两两互为独立的。 sub-digonal 和 super-digonal 上是相等的!
function triMat = GUE_matrix_MC_create_TriMat(size,seed)
%set random seed
rng(seed);
%set subdiagonal/superdigonal as chi-distributed
d=sqrt(1/2)*sqrt(chi2rnd(beta*[size:-1:1]))';
%set up digonal
d1=(randn(size,1));
triMat=spdiags(d,1,size,size)+spdiags(d1,0,size,size)+spdiags(d,1,size,size)';
end
这个方法确实好,通过观察(2.1)我们可以发现:
我们只需要 的存储空间。 他具有 tridigonal 和 irreducible 的结构(因为他的 sub-digonal 上的元素 a.s. 不等于 0),那我们就可以用一些比较厉害的算法来计算他最大的特征值了!比如说 bisection method(这个方法真的不错,感兴趣的可以看看这本书的 [4] lecture 30),他的算法复杂度只有 。
function [result] = step_TASEP_cdf(sigma,t,s)
s=step_TASEP_proper_interval(t,sigma,s);
c2=sigma^(-1/6)*(1-sigma^(1/2))^(2/3);
delta_t=c2^(-1)*t^(-1/3);
n=sigma*t;
MAX=(t+n-2*(sigma)^(1/2)*t-1/2)/(c2*t^(1/3));
for k=1:length(s)
if s(k)> MAX
result(k)=1;
else
s_resc=s(k)+delta_t;
x=s_resc:delta_t:MAX;
x=x';
result(k)=det(eye(length(x))-step_TASEP_kernel(t,sigma,x,x)*delta_t);%Bornemann Method
end
end
end
https://arxiv.org/pdf/0804.2543.pdf
这篇文章就是简单的介绍了一下有关于 random matrix 的算法,之后可能会陆续介绍一下 KPZ-universality 相关的东西,也就是我自己的方向,真的超级有趣!
参考文献:
[1] Dumitriu I, Edelman A. Matrix models for beta ensembles[J]. Journal of Mathematical Physics, 2002, 43(11): 5830-5847.
[2] ersson P O. Random matrices. Numerical methods for random matrices[J]. 2002.
[3] Bornemann F. On the numerical evaluation of Fredholm determinants[J]. Mathematics of Computation, 2010, 79(270): 871-915.
[4] Trefethen L N, Bau III D. Numerical linear algebra[M]. Siam, 1997.
编辑:于腾凯