블록 란초스 알고리즘
Block Lanczos algorithm컴퓨터 과학에서 블록 란초스 알고리즘은 길고 얇은 매트릭스에 의한 매트릭스의 곱셈만을 사용하여 유한한 영역에 걸쳐 매트릭스의 null space를 찾기 위한 알고리즘이다.그러한 행렬은 유한 필드 항목의 튜플 벡터로 간주되므로 알고리즘 설명에서 '벡터'라고 하는 경향이 있다.
블록 란초스 알고리즘은 2차적 체와 숫자 필드 체와 같은 정수 인자화 알고리즘의 최종 단계인 nullspaces를 찾는 것으로 알려진 가장 효율적인 방법 중 하나이며, 그 개발은 전적으로 이 애플리케이션에 의해 주도되어 왔다.
병렬화 문제
알고리즘은 본질적으로 평행하지 않다: 물론 매트릭스-벡터의 곱셈을 분산시킬 수는 있지만, 전체 벡터는 각 반복이 끝날 때마다 조합 단계에 사용할 수 있어야 하기 때문에 계산에 관련된 모든 기계는 동일한 고속 네트워크에 있어야 한다.특히 벡터를 넓히고 벡터의 슬라이스를 서로 다른 독립된 기계에 분산시키는 것은 불가능하다.
블록 위데만 알고리즘은 전체 매트릭스를 수용할 만큼 충분히 큰 여러 시스템을 사용할 수 있는 상황에서 더 유용하다. 그 알고리즘에서 시스템은 마지막 단계까지 독립적으로 실행될 수 있기 때문이다.
