계산 효율 : 희소 대 완전

Question

행렬이 (거의) 가득 찬 경우 스파 스에 저장하면 더 많은 시간이 계산된다는 사실을 알았습니다.

전체 매트릭스를 드문 드문 한 형태로 저장하는 것은 쉬운 일이 아니지만이 사실에 대한 이유를 알고 싶습니다.

내 생각에 스파 스에서 색인을 읽는 것이 계산 시간의 주요 원인이 될 것입니다. 다른 우아한 생각?

Answer 1

거의 전체 스파 스 매트릭스가 전체 매트릭스를 사용하는 것보다 계산 상으로 비싸다고하는 몇 가지 이유가 있습니다. 당신이 지적한 것처럼 가장 명백한 것은 스파 스 요소가 색인되어야한다는 것입니다 (일반적인 희소 매트릭스의 경우 Matlab은 Compressed Row Storage 체계를 사용합니다).

또 다른 명백한 속도 저하는 벡터화 및 프로세서로의 파이프 라이닝으로 인한 것입니다. 완전히 저장된 행렬의 경우 데이터는 깔끔하고 선형 인 형식이므로 작업을 쉽게 벡터화 할 수 있습니다. CRS와 같은 저장 체계의 경우, 특히 Matrix * Vector 연산에서 가장 많이 사용되는 경향이 있습니다 (예 : 방정식 시스템을 푸는 데 반복 솔버를 사용할 때). CRS 체계의 경우, 행렬을 가로 질러 이동하는 것은 좋은 선형 방식으로 프로세서에 공급 될 수 있지만, 행렬에 곱해진 벡터에서 끌어온 요소는 점프 할 것입니다.

Answer 2

는 다음의 밀도 행렬을 고려해

1 2 3 
4 5 6 
7 8 9 

I는 연속 블록에 저장하는 경우 :

1 2 3 4 5 6 7 8 9 

제가 직접 일부 행 및 열 번호를 부여 행렬의 요소를 액세스 할 기본 산술.

지금이 희소 행렬을 고려

지금

1 2 3 

된다 그러나 이것은 분명히에 대한 충분한 정보가되지 않도록 효율적으로이 행렬을 저장하기 위해

1 0 0 
0 0 2 
0 3 0 

, 나는 비 제로 요소를 폐기 행렬 벡터 곱셈과 같은 연산을 수행하십시오! 따라서 행렬에서 요소를 추출하려면 additional information을 추가해야합니다.

하지만 당신은 저장 방법의 관계없이이 행렬의 구조을 유지하기 위해 우리는 요소

스토어 자세한 정보에 액세스하는 추가 작업을 수행

1. 필요, 사용 볼 수 있습니다

여러분도 알다시피, 매트릭스의 구조를 보존하기 위해 저장하는 추가 정보를 보완하기 위해 매트릭스에 충분한 0이있는 경우에만 스토리지의 이점이 발생합니다. 예를 들어, Yale format에서 0이 아닌 숫자 (NNZ) 값이 (m(n − 1) − 1)/2보다 작 으면 m = 행 수이고 n = 열 수인 경우에만 메모리에 저장됩니다.