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

问题描述

我需要计算的几千元的小矩阵的零空间（8x9，4x3的不是因为我写了previously）并行（CUDA）。所有引用指向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?

推荐答案

要直接回答你的问题...是的！ QR分解！

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

设A是m×n矩阵秩ñ。 QR分解发现正交M-由米矩阵Q和上三角M-乘n矩阵R使得A = QR。如果我们定义：Q = [Q1，Q2]，其中Q 1是m乘n和Q2为米逐（MN），则Q2的列形成的甲^ 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分解的计算无论是革兰氏施密特，Givens旋转，或户主反射。他们有不同的稳定性能和操作数。

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屋！