RREF 대 LU 해결 복잡성

나는 A는 사각형이고, b는 열 벡터이다 도끼 = B를 해결하기 위해 두 가지 기본적인 방법의 실행 시간을 비교하여 '정신 테스트'오늘을 실행중인 :RREF 대 LU 해결 복잡성

A = rand(1000,1000); b = rand(1000,1); Xmat = zeros(1000,1001); 
    tic; [L,U] = lu(A); x = U\(L\y); toc; 
    tic; Xmat = rref([A b]); toc;

출력 : 무작위, 밀도 행렬을 위해 나는 LU 단계가 차례로 감소에 쉴론을 찾는만큼 비용에 대해 것 같다 가우스 소거법 (한 비용에 대한 것으로 예상하기 때문에

Elapsed time is 0.018528 seconds. 
    Elapsed time is 10.215791 seconds.

나는,이 차이는 놀라운 발견 내가 뭔가를 놓치지 않는 한 증대 된 매트릭스의 형태). 나는 하나의 벡터에 대해서 LU가 그렇게 잘 할 것이라고 기대하지 않았다. b. 불일치는 더 적은 선형 시스템 (예 : 100x100 행렬)에서도 지속됩니다. 여기 무슨 일 이니?

출처

2016-09-01 zeno

가우스 제거는 LU 계산 방법이 아닙니다. 또한 LU는 수십 년 동안 포트란 LAPACK에서 고도로 최적화 된 "원시적"분해입니다. rref 행 교체 및 피벗에 의해 matlab 수준에서 계산됩니다. 또한 rref은 매트릭스 항목을 검사하고 가능하면 rats 기능을 통해 항목을 소수 표현으로 변환합니다. 이는 rref에 큰 오버 헤드를줍니다. rref의 유일한 유스 케이스는 교육 또는 데모 용도이기 때문에. LU 분해만큼 수치 적으로 신뢰할 수 없습니다.

속도 차이가 있습니다.

심각한 계산을 수행하는 경우 rref을 사용하지 마십시오.

출처

2016-09-01 19:24:05 percusse

물론 심각한 계산에는 rref를 사용하지 않는다는 것을 알고 있습니다. 나는 불일치의 근원에 관심이 있었다. 그러나 나는 궁금합니다 - LU는 LAPACK에 따라 임의의 고밀도 매트릭스에 대해 "최적화 된"방법은 무엇입니까? – zeno

@zeno 또한 추가되었습니다. 설명이 필요한지 알려주세요. – percusse

RREF 대 LU 해결 복잡성

답변

관련 문제