尽可能快地计算矩阵的零空间 [英] Computing the null space of a matrix as fast as possible

问题描述

我需要并行 (CUDA) 计算数千个小矩阵(8x9，而不是我之前写的 4x3)的零空间.所有引用都指向 SVD，但数值配方中的算法似乎非常昂贵，并且给了我很多我并不真正需要的零空间以外的东西.高斯消除真的不是一种选择吗?还有其他常用的方法吗?

I need to compute the nullspace of several thousand small matrices (8x9, not 4x3 as I wrote previously) in parallel (CUDA). All references point to SVD but the algorithm in numerical recipes seems very expensive, and gives me lots of things other than the null space that I don't really need. Is Gaussian elimination really not an option? Are there any other commonly used methods?

推荐答案

直接回答你的问题...是的！二维码分解！

To answer your question directly... yes! QR decomposition!

设 A 是一个 m×n 矩阵，秩为 n.QR 分解找到正交 m×m 矩阵 Q 和上三角 m×n 矩阵 R，使得 A = QR.如果我们定义 Q = [Q1 Q2]，其中 Q1 是 m-by-n，Q2 是 m-by-(m-n)，那么 Q2 的列构成了 A^T 的零空间.

Let A be an m-by-n matrix with rank n. QR decomposition finds orthonormal m-by-m matrix Q and upper triangular m-by-n matrix R such that A = QR. If we define Q = [Q1 Q2], where Q1 is m-by-n and Q2 is m-by-(m-n), then the columns of Q2 form the null space of A^T.

QR 分解由 Gram-Schmidt、Givens 旋转或 Householder 反射计算.它们具有不同的稳定性属性和操作次数.

QR decomposition is computed either by Gram-Schmidt, Givens rotations, or Householder reflections. They have different stability properties and operation counts.

你说得对:SVD 很贵！我不能说最先进的东西使用了什么，但是当我听到计算零空间"(以一种对我来说很容易理解的方式)时，我会想到 QR.

You are right: SVD is expensive! I can't speak for what state-of-the-art stuff uses, but when I hear "compute null space" ( in a way that is simple for me to understand), I think QR.

这篇关于尽可能快地计算矩阵的零空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！