f****m 发帖数: 32 | 1 谁能帮忙给出CSR数据结构下的 Incomplete cholesky descompostion 算法?
想用 Incomplete cholesky conjugate gradient。
多谢! |
|
t*****n 发帖数: 467 | 2 Suppose you already obtained the cholesky decomposition for matrix A, is
there a fast way to get the cholesky decomposition for A+D? Here D is a
diagonal matrix.
Thank you very much for your input |
|
g****t 发帖数: 31659 | 3 你最后一句话是错的,至少是misleading.
例如Cholesky分解也需要这么做,但Cholesky基本上可以说是
numerical stability最强的求逆方法了. |
|
g*****u 发帖数: 14294 | 4 你可能得先琢磨一下LU分解算法可不可并行。这东西因为很基础很重要,所以从理论到
实践论述很多。你不妨检索一下。
一个特例是Cholesky分解,用得很多。你看看Cholesky分解并行算法里的Multi-
frontal类方法对你LU分解是否有启发。
这只是我的一点皮毛拙见,仅供参考。 |
|
d******e 发帖数: 7844 | 5 NMF和Cholesky Decomposition有毛关系啊。
NMF就是
min ||X-AB||_F^2+各种Regularizations
s.t. 各种Nonnegative Constraints
Cholesky是正定对称矩阵X分解为UU',U是个三角阵。 |
|
f**********d 发帖数: 4960 | 6 cholesky decomposition对positive definite hermitian matrix是唯一的。
怎么证明这一点? |
|
|
e***n 发帖数: 286 | 8 【 以下文字转载自 Computation 讨论区 】
发信人: erain (红花会大老板), 信区: Computation
标 题: 紧急求问: 是否可以将一个对称不定矩阵 A 分解为 A = B * B'
发信站: BBS 未名空间站 (Sat Apr 21 16:47:52 2007)
Urgent!
For any symmetric definite matrix, for sure we can factor it with Cholesky
method. How about symmetric indefinite matrix? I need factor such a matrix
A exactly into the product form
A = B * B'
where B' is the transpose of B and B is some n x n matrix ( not necessarily
to be triangular).
I know we can factor it with a LDLT method and fur |
|
|
c*****e 发帖数: 34 | 10 就是 ufl 的 Tim Davis 写的那个cholmod solver, 我用它做 cholesky
factorization,为什么很简单的 spd matrix 的factorization它都算不对? 是不是有
什么设置问题? 谢谢! |
|
c*****t 发帖数: 562 | 11 最好还是用javaspace的,偶想用一下,懒得自己编了,呵呵 |
|
k***s 发帖数: 277 | 12 【 以下文字转载自 Mathematics 讨论区 】
发信人: kenjs (乔峰.Leon), 信区: Mathematics
标 题: 一个矩阵分解的问题(对称实矩阵)
发信站: BBS 未名空间站 (Thu Nov 9 18:11:19 2006), 转信
cholesky decomposition (from matlab)
可以把实对称矩阵X分解为
R' * R = X
可是现在我需要的是把X分解为R,R也是upper trianglular matrix
R * R' = X
请问有没有什么现成的方法?(最好不要自己从头到尾coding) |
|
g****t 发帖数: 31659 | 13 各种precondition算法,都需要有经验,能把例外情况修补完毕,
对楼主可能太难了。我推荐Cholesky分解。省事省心。
如果只要估计解,那最省内存的方法其实是recursive least square之类的
东西,可以一行一行进数据。
电网? 你看B是不是symmetric diagonally dominant,是的话可以用ICCG。
规模大了比如 N > 1,000,000 可以试试algebraic multigrid preconditioned
conjugate gradient.
不过N才60000,这种问题按理说直接LU分解也耗不了那么多内存,你还是
先研究研究matlab里/和\的区别吧。 |
|
N******n 发帖数: 3003 | 14 有一个symmetric matrix, 我是平方得来的,应当是positive definite: 看了
eigvalue 都是正的,但是在matlab上用cholcov: Cholesky-like covariance
decomposition
出不来:
[T,err] = cholcov(sigma)
T是空的。不知道为什么,谢谢
A=
sigma =
0.4382 -0.3990 -1.2396 -1.0880 0.9084 1.5463 -0.6721 0.
4587
-0.3990 0.5448 1.3429 1.1029 -1.0068 -1.7077 0.6971 -0.
4047
-1.2396 1.3429 15.4717 10.6047 -10.6348 -18.3169 6.8657 -6.
0160
-1.0880 1.1029 10.6047 7.5741 -7.2716 -12.7805 4.8757 ... 阅读全帖 |
|
g****t 发帖数: 31659 | 15 PDE计算流体力学什么的,估计很多人没
有实际经验。就先不谈。
(实际上ai+pde也是一个方向。尽管不主流。)
ODE也不谈。
就说最简单的,2变量f(x,y)=0
代数方程求根,ai方法我不认为能赢正交函数展开算矩阵。
其实谁也不是傻子,要不然矩阵特征根为啥
不用ai,现有的库不都是cholesky之类的方法。
我再举个例子。不用硬件乘法,来实现浮点数乘法,
AI能赢CORDIC吗?
越是基本的问题,
in near future, 越是long way to go。 |
|
g****t 发帖数: 31659 | 16 应该就是一个是精确的最小二乘法。另一个是梯度或者别的办法近似求解?
精确的最小二乘法不应该有什么大问题。前面就是叠加。最后一步
3*3矩阵求逆那步用一下cholesky就够了。他的数很少。
若是近似方法,这个作者给的数据集太小。估计iid什么的也没测。
所以可能会对参数敏感。
: 这么快就放弃了? 你那个tensorflow的例子我已經调通了。
: 实在错的太离谱了。这种垃圾repository竟然有81个星我也是醉了。
: 想听的发包子过来,半个钟头后我给你们分析。
: Update:
: 这个竟然是一本书的配套代码,书要卖$23。突然我就觉得
: job security暴涨了。这种书卖越多越好。大家不要给它
: 提交补丁,最好初学者都死在这书上,我们老司机就安全了。
|
|
g****t 发帖数: 31659 | 17 二十年前我就肯定确定以及一定ann有用
我的硕士论文是ann
Ann本身就是非线性滤波器
怎么会没用? 我说的是单层神经网。还不是deep learning.
Ann能拿来更好的控制温箱的温度你信不信。
为什么一般公司没人用?
因为懂的人太少了
一般公司知道什么是矩阵的condition number
什么是cholesky分解的总共才有几个啊...
讲究ann过于扯淡了
更重要的是tool chain,tech stack不行
所以应用ann的成本是很高的。
但是你查查军工...
咱们不扯什么智能不智能
投入这么大的软件ecosystem ,
能没用吗?起码能普及个多线性代数吧!
起码统计学习的一堆指标和技术术语会
进入很多产品说明书吧?到时候别人都会的,你听不懂...
也可以很愉快?
哭天喊地说搞AI都是大骗子的,不如换个角度想想。
不用你当骗子,还能享受骗子的成果,这种美好的事,有什么好悲愤交加的呢...... |
|
N******n 发帖数: 3003 | 18 顺便帮我看看这个问题:
标 题: 问个简单的matrix变换的问题,包子答谢
发信站: BBS 未名空间站 (Thu Apr 10 15:27:16 2014, 美东)
有一个symmetric matrix, 我是平方得来的,应当是positive definite: 看了
eigvalue 都是正的,但是在matlab上用cholcov: Cholesky-like covariance
decomposition
出不来:
[T,err] = cholcov(sigma)
T是空的。不知道为什么,谢谢
A=
sigma =
0.4382 -0.3990 -1.2396 -1.0880 0.9084 1.5463 -0.6721 0.
4587
-0.3990 0.5448 1.3429 1.1029 -1.0068 -1.7077 0.6971 -0.
4047
-1.2396 1.3429 15.4717 10.6047 -10.6348 -18.3169 6.8... 阅读全帖 |
|
t*********g 发帖数: 6 | 19 我现在用cholesky分解去求逆矩阵,发现太慢,那位大侠知道
有没有优于O(n^3)的算法?多谢了。 |
|
w*****g 发帖数: 47 | 20 How to make draws which follow multivariate normal distribution? used the
subroutine to decompose the covariance matrix into cholesky factor. but can
not guarantee the matrix is positive definite. is all covariance matrix
positive definite? |
|
b***e 发帖数: 38 | 21 The level of fill-in makes a big difference. |
|
f****m 发帖数: 32 | 22 if the fill-in lever is 0 (ICCG0)? |
|
b***e 发帖数: 38 | 23
Zero-level fill-in seems to be not the best. The most effective choice is to
use drop-off tolerance. |
|
e***n 发帖数: 286 | 24 Urgent!
For any symmetric definite matrix, for sure we can factor it with Cholesky
method. How about symmetric indefinite matrix? I need factor such a matrix
A exactly into the product form
A = B * B'
where B' is the transpose of B and B is some n x n matrix ( not necessarily
to be triangular).
I know we can factor it with a LDLT method and further get
A = P * P' - Q * Q'
But this is not exactly what I need.
Thank you very much! |
|
c*****e 发帖数: 34 | 25 就是 ufl 的 Tim Davis 写的那个cholmod solver, 我用它做 cholesky
factorization,为什么很简单的 spd matrix 的factorization它都算不对? 是不是有
什么设置问题? 谢谢! |
|
|
k******n 发帖数: 35 | 27 I do not think LAPACK is a good choice in your case unless your problem is
really small.
I assume your matrices are dense. Since S and T are positive definite, S^{1/
2} and T^{1/2} can be obtained by Cholesky decomposition. To use LAPACK, K
has to be calculated explicitly. If you only a few singular values, this is
totally not necessary. Consider K as an operator and use ARPACK.
If the problem is small or you need all singular values, LAPACK will be your
choice. However, I would say Matlab will |
|
l*****i 发帖数: 3929 | 28 来自主题: Computation版 - 并行计算 incomplete LU/Cholesky factorization? |
|
c*******h 发帖数: 1096 | 29 来自主题: Computation版 - 并行计算 preconditioner跟本身的solver没什么关系,不同种类可以互相搭配的
我的确在往incomplete cholesky的方向去想。当然因为矩阵是满的,得指定sparse
pattern。某种程度上思路有点像approximate inverse |
|
c*******h 发帖数: 1096 | 30 来自主题: Computation版 - 并行计算 你有什么经验吗?
incomplete cholesky很容易break down
我以前老板就说,当初搞不完全分解的人都是冲着对角占优的矩阵去的
但是粒子系统的矩阵很少会对角占优的
真是头痛 |
|
k****n 发帖数: 81 | 31 if A'A is nonsigular, then you can try cholesky decomposition. maybe that
will help you some.
A |
|
e***n 发帖数: 286 | 32 【 以下文字转载自 Computation 讨论区 】
发信人: erain (红花会大老板), 信区: Computation
标 题: 紧急求问: 是否可以将一个对称不定矩阵 A 分解为 A = B * B'
发信站: BBS 未名空间站 (Sat Apr 21 16:47:52 2007)
Urgent!
For any symmetric definite matrix, for sure we can factor it with Cholesky
method. How about symmetric indefinite matrix? I need factor such a matrix
A exactly into the product form
A = B * B'
where B' is the transpose of B and B is some n x n matrix ( not necessarily
to be triangular).
I know we can factor it with a LDLT method and fur |
|
c*******h 发帖数: 1096 | 33 cholesky抽个系数出来就行了
或者lu抽个系数出来
都一样 |
|
h***o 发帖数: 26 | 34 A 如果正定, cholesky当然没有问题
关键 A 是非正定, 不知道你所说的抽个系数什么意思? |
|
c*******h 发帖数: 1096 | 35 x is the largest eigenvector of the generalized eigenvalue problem
Ax = aBx.
or simply speaking, let B have cholesky B=GG' and let y=G'x, then
f(x) = y' * (G^-1*A*G^-T) * y / y'y
so y is the largest eigenvector of G^-1*A*G^-T.
or more simply speaking, the maximum is attained when x is the
largest eigenvector of A*B^-1 or B^-1*A
definite. |
|
b*****n 发帖数: 78 | 36 谢谢各位的答复。我是学工程的,数学相对弱点。
我今天找了些generalized eigenvalue problem方面的书,发现答案是B^{-1}*A的最大
eigenvalue.
有个问题需要继续请教:
为什么要用 cholesky decomposion, B=GG'? 这样可以吗?
f(x) = X(x)/Y(x),
where X(x) = (Px)^{T} P^{-T}*A*P^{-1} *(Px)
and Y(x) = (Px)^{T}*(Px),
where P = P^{T} = B^{1/2}.
令 y=Px, 这样的答案是P^{-T}*A*P^{-1}的最大eigenvalue
谢谢 |
|
c*******h 发帖数: 1096 | 37 你说的开平方也是B的一种分解,只要B是正定,分解有无数种,都可以用,最后答案一样
深入一点说,矩阵开平方运算与cholesky,与特征分解,与svd有非常紧密的联系
还有就是你可以直接算B^-1*A或者A*B^-1的最大特征值,这样最省事,只不过当
B的条件数比较大的时候误差相对来说大一点 |
|
c*******h 发帖数: 1096 | 38 if well done, this can be a nice SIMAX paper...
ok, back to the topic. my guess is no. the diagonal elements affects
all other elements. so an update takes at least qradratic time.
but is there an update method faster than cubic? no---just a guess. |
|
h*y 发帖数: 1289 | 39 Sorry, it should be Cholesky factor. |
|
d*j 发帖数: 13780 | 40 n1 + sqrt(1-pho^2)n2
if n-dim correlation matrix, cholesky decomposition |
|
p*****w 发帖数: 82 | 41 第一道题:
2x2:当然很简单了。
4x4:把4x4分成四个2x2的平方。带洞的2x2很容易铺。
只要稍微证明一下剩下三个2x2平方可以用2x1铺满即可。
8x8:把它分成四个4x4平方。洞肯定属于其中一个平方。用前面结论证明即可。
同理推出2^n X 2^n。
第二道:
有点罗嗦。好像是heard on street 上一道题的翻版或改版?
第三道:
是不是P(H|H)=P(H&H)/P(H)=P(H) (假设两次抛coin是独立的)
第四道题:
只要求出correlation matrix 的cholesky decomposition,再乘上随机生成独立的随机数序列,即可。 |
|
a*z 发帖数: 294 | 42 cholesky decomposition? |
|
s***e 发帖数: 267 | 43 1.如果没有其他条件,只是要求population correlation是0.6, 可以用normal和
cholesky分解:
X 是2维standard normal, A=[1, 1/3; 1/3, 1],则Y=A*X的两个元素满足条件。
2.skewness是measure是否对称的parameter。normal的变量的skewness都是0。没有其
他限制可以用一个简单的不对
称分布构造,比如bernoulli(p). 给定skewness可以计算p的值,就是要解一个二次方
程(可能需要rescale)。kurtosis
是measure分布的tail是否light/heavy的parameter。可以用laplace distribution或
者bernoulli来构造。 |
|
|
o*p 发帖数: 77 | 45 problem 3
1/4 ?
suppose x,y are N(0,1)
then Cholesky decomposition x=rho*y+sqrt(1-rho^2)*z
y, z are independent
rho is correlation between x and y =1/sqrt(2)
draw graph in y ,z plane
then p(x>0|y<0)
=p(x>0 intersect with y<0)/p(y<0)=(1/8)/(1/2)=1/4 |
|
t*****e 发帖数: 38 | 46 约好2点, 1点55找了个没人的位置(很难找),等到2点15分,还没来电话。回到工作
岗位,突然打来了。没有道歉,直接开始。
1.what is your strongest area? math,statistics,然后从统计开始
2. give me 3 important result of prob theory. This was OK.
3. what is the prob that A
result after computation, any other way, I gave an intuitive way, any other
way, I said sorry, he said" I have a better way I thought you could have
used,I am a little bit disappointed"
4. How could you generate a normal from uniform? I said use sum... 阅读全帖 |
|
T*****w 发帖数: 802 | 47 Two independent random variables uniformly distributed in [0,1]. How do you
transform them, so that they stay uniformly distributed in [0,1], but the
correlation between them becomes \rho.
不知道如何用copula的方法去解?
(另外:类似的题目是如果是两个 normally distributed z1, z2 ~N(0,1),(independently)
可以用 cholesky decomposition 的方法得到
x1=z1
x2=pz1 + sqrt(1-p^2) z2 |
|
|
A**u 发帖数: 2458 | 49 不对
choleski是A = B * B转置
题目要求 B=B |
|
f*******a 发帖数: 663 | 50 Incomplete Cholesky Conjugate Gradients |
|