Schnellste Lösung kleiner homogener linearer Systeme mit Eigen

Question

Ich muss viele kleine (n = 4) homogene lineare Systeme der Form Ax = 0 lösen, wobei A eine singuläre Matrix ist. Ich verwende derzeit den folgenden Code:

void solve(const matrix_t& A, vector_t& x){ 
    auto svd = A.jacobiSvd(Eigen::ComputeFullU | Eigen::ComputeFullV); 
    auto V = svd.matrixV(); 
    x = V.col(A.rows() - 1); 
    x.normalize(); 
} 

Gibt es schnellere Möglichkeiten, das zu tun?

Answer 1

Der schnellste Weg, um den Nullraum einer allgemeinen Matrix mit Eigen zu erhalten, ist die Verwendung seiner LU-Zerlegung. In der Praxis verwende ich die Householder-QR-Zerlegung anstelle von LU, weil sie stabiler zu sein scheint, wenn die Eingabematrix nicht perfekt singulär ist. QR ist immer noch viel schneller als die in der Frage vorgeschlagene SVD und gibt sehr ähnliche Ergebnisse für meine Probleme. https://eigen.tuxfamily.org/dox/group__DenseDecompositionBenchmark.html

-Code zur Berechnung der Nullraum mit LU, QR und SVD (Anmerkung: x.normalize() ist nicht erforderlich, aber hilfreich zum Vergleich die Lösungen):

template<typename matrix_t, typename vector_t> 
void solveNullspaceLU(const matrix_t& A, vector_t& x){ 
    x = A.fullPivLu().kernel(); 
    x.normalize(); 
} 

template<typename matrix_t, typename vector_t> 
void solveNullspaceQR(const matrix_t& A, vector_t& x){ 
    auto qr = A.transpose().colPivHouseholderQr(); 
    matrix_t Q = qr.householderQ(); 
    x = Q.col(A.rows() - 1); 
    x.normalize(); 
} 

template<typename matrix_t, typename vector_t> 
void solveNullspaceSVD(const matrix_t& A, vector_t& x){ 
    x = A.jacobiSvd(Eigen::ComputeFullV).matrixV().col(A.rows() - 1); 
    x.normalize(); 
}