희소 행렬로 이차 형태 행렬 곱셈을위한 알고리즘

Question

나는 맞춤형 행렬 라이브러리에 의존하는 코드를 최적화하고 있습니다. (이것은 어디에서나 존재하기 때문에 프로젝트에서 제외되지 않습니다.) 좋지는 않지만 사실입니다. ..) 많은 계산이 10 ~ 20 행과 열의 행렬로 완료, 많은 계산이 나는 종종 A가 드문 드문 것을 깨달았다 나는이 사실을 활용하고자하는

C = A*B*A' 

같은 차 형태를 포함한다. 그래서이 사건을 처리 할 알고리즘을 찾고 있습니다. 수치 안정성이 중요합니다. 내가 사용할 수 있는게있어? (우리 라이브러리를 작성하지 않았으므로 고려해야 할 함정이 있는지 모르겠습니다.)

"우리"의 단순 O (n^3) 곱셈 방법은 Eigen 3보다 빠르게 실행됩니다. 대상 플랫폼은 수치 안정성이 필요하고 행렬이 그리 크지 않기 때문에 Strassen의 알고리즘은 물론 Coppersmith-Winograd 알고리즘이 내가 원하는 알고리즘이 아닌 것 같습니다. 대신 A에서 0을 쉽게 확인할 수있는 방식으로 2 차 형식 곱하기입니다.

어떤 의견을 보내 주셔서 감사합니다!

Answer 1

빠른 희박 매트릭스 곱셈을 다루는 this 종이가 있습니다. 개발 된 알고리즘은 스파 스 매트릭스를 두 부분으로 나눕니다 : 조밀하고 희소 한 부분으로 빠른 곱셈 알고리즘을 적용합니다. 그래서 제게 Strassen과 관련하여 언급 한 것처럼, 행렬의 크기에 의존하지 않는 것처럼 보입니다. 그러나 그것이 드문 드문 사실입니다.

Answer 2

조밀 한 매트릭스보다 응축 된 방식으로 스파 스 매트릭스를 구현하는 방법이 있습니다. I는 다음대로 수행 편도

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0] 

대신 O의 비 - 제로 엘리먼트

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*; 

따라서 매트릭스 이제 O (N)의 공간 복잡도를 갖는 선형 어레이 (진다 A와 B가 행렬 인 A * B의 경우 일치하는 요소 (즉 a-> row == b-> col & & a-> col == b-> col)에 대해 각 배열을 탐색하기 만하면됩니다. 행), 여러 항목을 함께 추가 할 수도 있습니다 (내부 제품). 이 알고리즘은 O (n^3)보다는 O (n^2) 복잡도가됩니다. 이것은 제로가 될 내적 제품을 가져가는 경박 한 작업을 건너 뛸 수 있기 때문입니다.

Answer 3

체크 아웃 Highly Parallel Sparse Matrix-Matrix Multiplication algorothm