标签: linear-algebra

R有一个qr()函数,它使用LINPACK或LAPACK执行QR分解(根据我的经验,后者的速度提高了5%).返回的主要对象是包含在上三角矩阵R(即R=qr[upper.tri(qr)])中的矩阵"qr" .到现在为止还挺好.qr的下三角部分包含Q"紧凑形式".一个可以通过使用提取QR分解Q qr.Q().我想找到倒数qr.Q().换句话说,我确实有Q和R,并希望将它们放在"qr"对象中.R是微不足道的,但Q不是.目标是应用它qr.solve(),这比solve()在大型系统上快得多.

取两个3x3矩阵的乘积A*B=C.天真地,这需要使用标准算法进行 27次乘法.如果一个人很聪明,你可以只使用23次乘法来做到这一点,这是拉德曼于1973年发现的结果.该技术涉及保存中间步骤并以正确的方式组合它们.

现在让我们修改一个语言和一个类型,比如说C++的元素double.如果Laderman算法是硬编码而不是简单的双循环,那么我们是否可以期望现代编译器的性能能够消除算法的差异？

关于这个问题的注释:这是一个编程站点,问题是在时间关键内循环的最佳实践的上下文中提出的; 过早优化这不是.关于实施的提示非常受欢迎.

我有一个大的NxN密集对称矩阵,并希望特征向量对应于k个最大特征值.找到它们的最佳方法是什么(最好是使用numpy,但也许通常使用blas/atlas/lapack,如果这是唯一的方法)？通常,N比k大得多(比如N> 5000,k <10).

如果我的起始矩阵稀疏,Numpy似乎只有找到k个最大特征值的函数.

什么是最好的(在简单的使用和性能方面)C++/C++ 11库可以简化如下的公式？

(a < 0 && b > 0) || (a < 0 && c > 0) || (a < 0 && c > 1) 

到(例如)

a < 0 && (b > 0 || c > 0)

我认为解释一件事是非常重要的(因为我看到这个问题被误解了).

我不想简化C/C++表达式 - 我知道,编译器可以实现它.

我正在制作一个图形处理工具.在图形的边缘,有让关于其顶点某些情况下(比如顶点是a,b,c和这些条件都一样a<b,b>0等等-请注意,这些条件不表示为"弦",他们可以是任何功能或图书馆电话).在处理过程中,我正在收集表达式,在进一步的图形处理之前,我想简化它们.

条件和表达式将在运行时创建.

我希望能够向该库输入一些表达式,例如:

[...]
a = new Variable();
b = new Variable();
expr1 = lib.addExpr(a,0, lib.LESS);
expr2 = lib.addExpr(b,0, lib.MORE);
expr3 = lib.addExpr(expr1, expr2, lib.AND);
[...]
cout << lib.solve(exprn).getConditionsOf(a); …

如何从矩阵中识别线性​​独立的行？例如,

第4行是独立的.

有没有一种方法可以调用在python中创建一个随机的标准正交矩阵？可能使用numpy？或者有没有办法使用多个numpy方法创建一个正交矩阵？谢谢.

一般

我正在寻找一个能够在大型有限域上进行精确计算的库,例如GF(2 ¹²⁸)/ _{2 ¹²⁸}和GF(2 ²⁵⁶)/ _{2 ²⁵⁶}.我列出了我需要的功能以及下面很酷的功能.显然,图书馆应尽可能快:-).啊,因为我不是C++主人(可能大多数库是C++),所以示例代码生成一个随机元素/一个常量并将其乘以它的乘法逆

必备功能

• 增加了田野元素
• 场元素的乘法
• 找到字段元素的乘法逆

很高兴有特色

• 矢量/矩阵支持
• 随机元素支持

我已经看过的图书馆可能不会起作用

• FFLAS/FFPACK似乎不适用于如此大的有限域
• Givaro似乎没有在如此大的有限领域工作

我已经看过的图书馆可以工作(但我无法使用)

• NTL,我无法反转一个元素,但它应该真的有效,因为SAGE似乎在定义GF(2 ^ 256)时使用这个库,并且可以使用它来反转元素x^(-1)
• PARI/GP,我无法在文档中找到我需要的所有内容,但是SAGE文档有点说它应该可以工作

其他说明

• 我正在编写一个Haskell程序,稍后将接口该库,因此更容易Haskell接口更好:-)

Eigen是否具有存储密集,固定大小,对称矩阵的有效类型？(嘿,它们无处不在!)

即N = 9,它应该只存储(1 + 9)*9/2 == 45个元素并且它具有适当的操作.例如,应该有效地添加两个对称矩阵,其返回相似的对称矩阵.

如果没有这样的事情,那么哪些动作(看起来像这样)我应该把这种类型介绍给Eigen？它有"观点"的概念吗？我可以为自己的类型写一些类似"矩阵视图"的东西,这会让它成为特征性的吗？

PS可能我可以使用map将普通数组视为1xN矩阵,并对其进行操作.但这不是最干净的解决方案.

我在matlab中编写梯度下降.对于两个功能,我得到了更新步骤:

temp0 = theta(1,1) - (alpha/m)*sum((X*theta-y).*X(:,1));
temp1 = theta(2,1) - (alpha/m)*sum((X*theta-y).*X(:,2));
theta(1,1) = temp0;
theta(2,1) = temp1;

Run Code Online (Sandbox Code Playgroud)

但是,我想要对此代码进行矢量化,并能够将其应用于任意数量的功能.对于矢量化部分,有人向我指出,我想要做的是矩阵乘法

theta = theta - (alpha/m) * (X' * (X*theta-y));

Run Code Online (Sandbox Code Playgroud)

这很好看,但是当我尝试时,我意识到它不适用于梯度下降,因为参数不会同时更新.

然后,我如何矢量化此代码并确保参数并同时更新？

我想解决Ax = b,其中A是一个非常大的正方形正定对称块矩阵和x和b是矢量.当我说大的时候我指的是nxn一个n大到的矩阵300,000.

这是一个我想要解决的更小但有代表性的矩阵的例子.

这里是相同的矩阵放大显示它由密集的matricies块组成.

我以前(看到这里,这里,并且在这里)使用了Eigen的Cholesky解算器,它工作得很好,n<10000但与n=300000Cholesky求解器相比太慢了.但是,我没有利用我有块矩阵的事实.显然,存在用于求解稀疏块矩阵的算法(例如,块cholesky分解).

我想特别知道Eigen是否已经使用因子分解或迭代方法对我可以使用的稀疏密集块矩阵进行了优化算法？

你也可以建议其他算法可能是解决我的矩阵的理想选择吗？我的意思是,据我所知,至少对于因子分解发现排列矩阵是NP难以存在很多不同的启发式方法,并且据我所知,人们建立了不同矩阵结构的直觉(例如带状矩阵)以及哪种算法效果最好跟他们.我还没有这种直觉.

我目前正在研究使用共轭梯度法.我自己用C++实现了这个,但仍然没有利用矩阵是一个块矩阵的事实.

//solve A*rk = xk
//Eigen::SparseMatrix<double> A;
//Eigen::VectorXd rk(n);
Eigen::VectorXd pk = rk;

double rsold = rk.dot(rk);
int maxiter = rk.size();
for (int k = 0; k < maxiter; k++) {
    Eigen::VectorXd Ap = A*pk;  
    double ak = rsold /pk.dot(Ap);
    xk += …