4×4 행렬의 행렬 곱셈을위한 좋은 성능 알고리즘이 무엇인지 궁금합니다. 일부 아핀 변환을 구현하고 있으며 Strassen과 같은 효율적인 행렬 곱셈을위한 여러 알고리즘이 있음을 알고 있습니다. 그러나 그렇게 작은 행렬에 특히 효율적인 알고리즘이 있습니까? 내가 본 대부분의 소스는 점근 적으로 가장 효율적인 소스를 찾고 있습니다.
댓글
Answer
Wikipedia는 두 개의 nxn 행렬의 행렬 곱셈 에 대한 4 개의 알고리즘을 나열합니다.
프로그래머가 작성하는 고전적인 알고리즘은 O (n 3 )이며 “Schoolbook matrix multiplication”으로 나열됩니다. 네. O (n 3 )는 약간의 히트작입니다. 차선책을 살펴 보겠습니다.
Strassen 알고리즘 은 O (n 2.807 )입니다. 이 방법은 작동합니다. 몇 가지 제한이 있으며 (예 : 크기는 2의 거듭 제곱 임) 설명에주의 사항이 있습니다.
기존의 행렬 곱셈과 비교할 때 알고리즘은 더하기 / 빼기에 상당한 O (n 2 ) 워크로드를 추가합니다. 따라서 특정 크기 이하에서는 기존의 곱셈을 사용하는 것이 더 좋습니다.
이 알고리즘과 그 기원에 관심이있는 사람들은 Strassen은 어떻게 행렬 곱셈 방법을 고안 했습니까? 는 좋은 읽기가 될 수 있습니다. 추가 된 초기 O (n 2 ) 워크로드의 복잡성에 대한 힌트를 제공하고 이것이 기존 곱셈을 수행하는 것보다 더 많은 비용이 드는 이유를 알려줍니다.
그래서 실제로는 는 O (n 2 + n 2.807 )이며 큰 O를 작성할 때 낮은 지수 n 에 대한 비트는 무시됩니다. 좋은 2048×2048 매트릭스에서 작업하고 있다면 유용 할 수 있습니다. 4×4 매트릭스의 경우 오버 헤드가 다른 시간에 소모되기 때문에 속도가 느려질 수 있습니다.
그리고 Coppersmith–Winograd가 있습니다. 알고리즘 은 O (n 2.373 )이며 약간의 개선 사항이 있습니다. 또한주의 사항이 있습니다.
Coppersmith-Winograd 알고리즘은 이론적 시간 경계를 증명하기 위해 다른 알고리즘의 빌딩 블록으로 자주 사용됩니다. 그러나 Strassen 알고리즘과는 달리 매트릭스가 너무 커서 할 수없는 이점 만 제공하기 때문에 실제로 사용되지 않습니다. 최신 하드웨어로 처리됩니다.
그러므로 초대형 매트릭스에서 작업 할 때 더 좋지만 4×4 매트릭스에는 유용하지 않습니다.
p>
이 내용은 행렬 곱셈 : Sub-cubic 알고리즘 의 wikipedia 페이지에 다시 반영되어 더 빠르게 실행되는 이유를 알 수 있습니다.
알고리즘이 존재합니다. 간단한 것보다 더 나은 실행 시간을 제공합니다. 가장 먼저 발견 된 것은 1969 년 Volker Strassen이 고안 한 Strassen의 알고리즘으로 “고속 행렬 곱셈”이라고도합니다.이 알고리즘은 두 개의 2 × 2- 행렬을 곱하는 방법을 기반으로합니다. 일반적인 8), 여러 추가 덧셈과 뺄셈 연산이 필요합니다. 이것을 재귀 적으로 적용하면 곱셈 비용이 O (n log 2 7 ) ≈ O (n 2.807 ). Strassen의 알고리즘은 더 복잡하고 순진한 알고리즘에 비해 수치 적 안정성이 떨어집니다.하지만 다음과 같은 경우 더 빠릅니다. n> 100 정도이며 BLAS와 같은 여러 라이브러리에 나타납니다.
알고리즘이 더 빠른 이유의 핵심입니다. 일부 수치 안정성 및 추가 설정. 4×4 매트릭스에 대한 추가 설정은 더 많은 곱셈을 수행하는 비용보다 훨씬 큽니다.
이제 귀하의 질문에 답하십시오.
하지만 그렇게 작은 행렬에 특히 효율적인 알고리즘이 있습니까?
아니요, O (n 3 ) 하나가 상당히 합리적으로 작동하기 때문에 4×4 행렬 곱셈에 최적화 된 알고리즘이 없습니다. 오버 헤드로 큰 히트를 감수 할 의사가 있음을 발견하기 시작할 때까지. 특정 상황에서는 행렬에 대한 특정 사항을 미리 알 수있는 오버 헤드가있을 수 있지만 (예 : 일부 데이터가 재사용 될 수있는 양) 정말 가장 쉬운 방법은 O (n 3 ) 솔루션을 사용하고 컴파일러가 처리하도록하고 나중에 프로파일 링하여 실제로 코드가 행렬 곱셈에서 느린 지점인지 확인합니다.
Math.SE 관련 : 4×4 행렬을 반전하는 데 필요한 최소 곱셈 수
답변
더 복잡한 알고리즘은 일반적으로 약간의 오버 헤드를 추가하는 일부 변환을 사용하기 때문에 단순한 알고리즘이 매우 작은 집합에서 가장 빠릅니다. 가장 좋은 방법은보다 효율적인 알고리즘 (대부분의 라이브러리가 간단한 방법을 사용한다고 생각합니다)이 아니라 SIMD 확장 (x86 또는 amd64 코드 가정)을 사용하거나 어셈블리로 직접 작성한 것과 같은보다 효율적인 구현에 있다고 생각합니다. . 또한 메모리 레이아웃을 잘 고려해야합니다. 이에 대한 충분한 리소스를 찾을 수있을 것입니다.
답변
4×4 매트 / 매트 곱셈의 경우 알고리즘 개선이 종종 이루어집니다. . 기본적인 cubic-time 복잡도 알고리즘은 꽤 잘 작동하는 경향이 있으며 그보다 더 멋진 것은 시간을 개선하기보다는 저하 될 가능성이 더 큽니다. 일반적으로 “확장 성 요소가 관련되지 않은 경우 (예 : 간단한 삽입 또는 버블 정렬이 아닌 6 개의 요소를 항상 포함하는 배열을 빠르게 정렬하려는 경우) 고급 알고리즘은 적합하지 않습니다. 참조의 지역성을 개선하기 위해 여기에서 매트릭스 전치와 같은 것들은 또한 전체 매트릭스가 하나 또는 두 개의 캐시 라인에 들어갈 수있을 때 실제로 참조의 지역성을 지원하지 않습니다. 이러한 종류의 미니어처 스케일에서 4×4 매트 / 매트 곱셈을 한꺼번에 수행하는 경우 일반적으로 적절한 캐시 라인 정렬과 같은 명령 및 메모리의 마이크로 레벨 최적화에서 개선이 이루어집니다.
댓글
- 대답입니다! 저는 ' SoA 약어에 대해 들어 본 적이 없습니다 (적어도 네덜란드어에서는 ' seksueel overdraagbare aandoening '는 ' 성병 ' …을 의미하지만 ' 여기서 의미하는 바가 아니기를 바랍니다.) 이 기술은 분명해 보입니다. ' 그 이름이 있다는 사실이 놀랍습니다. SoA는 무엇을 의미합니까?
- @Ruben 구조의 배열과 반대되는 배열의 구조. SoA는 가장 중요한 경로에 대해 가장 잘 저장되는 PITA 일 수도 있습니다. 다음은 ' 제목에 대해 찾은 멋진 작은 링크입니다. stackoverflow.com/questions/17924705/ …
- C ++ 11 / C11
alignas.
답변
4×4 만 곱하면된다는 것을 알고있는 경우 일반 알고리즘에 대해 전혀 걱정할 필요가 없습니다. 두 개의 포인터 만 가져 와서 다음을 사용할 수 있습니다.
(이를 자동화 된 방식으로 번역하는 것이 좋습니다).
그러면 컴파일러는 모든 것을 볼 수 있고 동적 루프가 없으며 제어 흐름이 없기 때문에이 코드를 최적화 (부분 합계 재사용, 수학 재정렬 등) 할 수있는 최적의 위치에 있습니다.
이 코드 없이는 이길 수 있다고 상상하기 어렵습니다. 내장 함수를 사용합니다.
Answer
n를 다르게 정의하면 점근 복잡도를 직접 비교할 수 없습니다. 목록과 같은 플랫 데이터 구조에서 알고리즘의 복잡성을 비교하는 데 익숙합니다. 여기서 n는 총 요소 수로 정의됩니다. 그러나 매트릭스 알고리즘은 n를 한 쪽 변 의 길이로만 정의합니다.
, 인쇄하기 위해 각 요소를 한 번 보는 것처럼 간단합니다. 일반적으로 O (n)이라고 생각하는 것은 O (n 2 )입니다. . n를 행렬의 총 요소 수로 정의하면 (예 : 4×4 행렬의 경우 n = 16) 순진 행렬 곱셈은 O (n 1.5 ), 꽤 좋습니다.
귀하의 최선의 방법은 O (n 3 )가 n가 플랫 데이터 구조와 비슷하게 정의 된 것만큼이나 나쁩니다.
0 0 0 1이므로 3D에 대한 아핀 변환이 4×3 부분 행렬 만 변경한다는 점에 주목하여 얻을 수있는 일부 성능입니다. 따라서이 행을 곱하는 것을 피할 수 있습니다.