바리스 알고리즘

Bareiss algorithm

수학에서, Erwin Bareiss의 이름을 딴 바리스 알고리즘은 정수 산술만을 사용하여 정수 입력으로 매트릭스의 결정인자 또는 에셀론 형태를 계산하는 알고리즘이다. 수행되는 모든 눈금은 정확하다고 보장된다(남은 없음).또한 이 방법은 입력에 이미 존재하는 것 이상의 반올림 오차가 유입되지 않도록 실제 입력(추정)으로 행렬의 결정요인을 계산하는 데도 사용할 수 있다.

역사

일반 바리스 알고리즘은 토플리츠 행렬에 대한 바리스 알고리즘과는 구별된다.

스페인어를 사용하는 일부 국가에서는 이 알고리즘을 바리스-몬탄테라고도 하는데, 이는 제자들 사이에서 이 방법을 대중화한 멕시코의 우니베르시다드 오토노마 데 누에보 레온의 교수인 르네 마리오 몬탄테 파르도 때문이다.

개요

결정론적 정의는 곱셈, 덧셈, 뺄셈 연산만을 가지고 있다.모든 행렬 항목이 정수일 경우 결정요인은 정수임.그러나 O(n!) 연산이 필요하기 때문에 정의나 라이프니즈 공식을 사용한 결정인자의 실제 연산은 비현실적이다.

가우스 제거는 O(n3) 복잡성을 가지지만 분열을 도입하여 부동 소수점 숫자를 사용하여 구현하면 반올림 오류가 발생한다.

모든 숫자를 부동 소수 대신 정수 분수로 유지하면 반올림 오류를 피할 수 있다.그러나 각 원소의 크기는 행 수에 따라 기하급수적으로 커진다.[1]

바리스는 중간 계수의 크기를 합리적으로 작게 유지하면서 정수를 보존하는 제거를 수행하는 문제를 제기한다.다음 두 가지 알고리즘이 제안된다.[2][3]

  1. Division-free 알고리즘 — Division 연산 없이 삼각형 형태로 매트릭스 감소를 수행한다.
  2. Fraction-free 알고리즘 — 중간 항목을 더 작게 유지하기 위해 분할을 사용하지만 Sylvester's Identity 때문에 변환은 여전히 정수 보존 상태(분할 잔량이 0개 있음)

완전성을 위해 Bareiss는 또한 부분 생성 곱셈 없는 제거 방법을 제안한다.[2]

알고리즘

이 알고리즘의 프로그램 구조는 표준 가우스 제거에서와 같이 단순한 트리플 루프다.그러나 이 경우 매트릭스는 각 Mk,k 항목이 선행 주계약 부차[M]k,k를 포함하도록 수정된다.알고리즘의 정확성은 k에 대한 유도로 쉽게 나타난다.[4]

  • 입력: M — n-제곱 행렬
    주요 미성년자[M]k,k가 모두 0이 아니라고 가정한다.
  • M0,0 = 1로 설정(참고: M은0,0 특수 변수)
  • 1에서 n-1까지 k인 경우:
    • k+1에서 n까지 i의 경우:
      • k+1에서 n까지 j의 경우:
        • Set
  • 출력: 매트릭스가 내부로 수정되고,
    각 Mk,k 항목에는 선행 부차[M]가 포함되어 있다.k,k
    항목 M은n,n 원래 M의 결정 인자를 포함한다.

주요 미성년자에 대한 가정(예: M = 0)과k−1,k−1i,k−1 일부 M 0 0(i = k, ...,n)이 거짓으로 판명되면 i번째 행과 k-1 행을 교환하고 최종 답변의 부호를 변경할 수 있다.

분석

바리스 알고리즘을 실행하는 동안 계산되는 모든 정수는 입력 매트릭스의 하위 계층의 결정 요인이 된다.이것은 Hadamard 불평등을 이용하여 이 정수들의 크기를 묶을 수 있게 한다.그렇지 않으면 바리스 알고리즘은 가우스 제거의 변형으로 볼 수 있으며 대략 동일한 수의 산술 연산이 필요하다.

따라서 각 항목에 대한 최대(절대) 값 2의L n × n 행렬에 대해, 바리스 알고리즘은 필요한 중간 값의 절대값에서 O(nn/2nL 2)를 경계한 채 O(n3) 초등 연산에서 실행된다.따라서 연산 복잡성은 기초 산술 사용 시 O(nL52(log(n)2 + L2) 또는 빠른 곱셈을 사용하여 O(nL4(log(n) + L))이다.

참조

  1. ^ Middeke, J.; Jeffrey, D.J.; Koutschan, C. (2020), "Common Factors in Fraction-Free Matrix Decompositions", Mathematics in Computer Science, 15 (4): 589–608, arXiv:2005.12380, doi:10.1007/s11786-020-00495-9
  2. ^ a b Bareiss, Erwin H. (1968), "Sylvester's Identity and multistep integer-preserving Gaussian elimination" (PDF), Mathematics of Computation, 22 (103): 565–578, doi:10.2307/2004533, JSTOR 2004533
  3. ^ Bareiss, Erwin H. (1966), MULTISTEP INTEGER-PRESERVING GAUSSIAN ELIMINATION (PDF). (작업 순서에 대한 더 명확한 그림 포함)
  4. ^ Yap, Chee Keng (2000), Fundamental Problems of Algorithmic Algebra, Oxford University Press