내 워크 스테이션에서 ~ 12000 개의 알 수없는 문제 (~ 12000 제곱, 비대칭, 비대칭 행렬)로 scipy.linalg.solve (LAPACK의 gesv 함수라고 부름)을 사용하면 좋은 대답을 얻을 수 있습니다. 10-15 분.대형 매트릭스에서 scipy.linalg.solve (LAPACK gesv)의 시간 복잡도?
가능 한도의 한계를 조사하기 만하면 (근본적으로 "유용함"이라고 말하지 않음), 근본적인 문제의 해결을 두 배로하여 ~ 50000 개의 미지를 해결할 필요가 생겼습니다. 스왑의 GBytes를 10 기가 바이트 이상 추가하면 이것이 기술적으로 내 워크 스테이션에서 실행되지만 적절한 RAM을 갖춘 일부 HW를 사용하는 것이 현명하고 AWS EC2 하이 - 메모리 쿼드 러플 엑스트라 라지에서 쫓아 냈습니다. .. 마지막으로 멀리 갈기 갈기 찢어진 곳 14 시간 (어이, 스팟 인스턴스는 값이 쌉니다.) 얼마나 멀리 있는지를 말하기는 불가능합니다.
불행히도, 관련된 솔버의 시간 복잡도가 (내 google-fu는이 문제에서 나를 실망 시켰습니다) 무엇인지 전혀 몰랐습니다. O (N^2)이면 약 4 시간 후에 끝나기를 기대했습니다. O (N^3)이면 16 시간 후에 끝날 것입니다. 물론 그것은 N을 4 배가되는 미지의 수로 해석합니다. 매트릭스의 요소 수가 16 배 증가했습니다!
내게 (프로젝트) 평생에 완료 할 수있는 기회가 있는지 또는 감사하지 않았는지 결정하는 데 도움이되는 조언!
기타 정보 :
스파 스 매트릭스 여기에 관심이없는 (내 행렬은 조밀하고, 어떤 경우에 scipy 년대에도 64 비트에 이상 2**31 비 - 제로 요소가 작동하지 않습니다).
워크 스테이션에서 Debian/Squeeze의 scipy, EC2의 Ubuntu 12.04를 사용하고 있습니다. 두 가지 모두 64 비트입니다.
gsev -> LU 분해 -> 위키 피 디아는 복잡성> ~ O (N^2.4)이지만 상수 요소 등은 무엇입니까? 이 작업 속도를 높이려면 OpenBlas 또는 Intel MKL과 같은 항목을 확인하는 것이 좋습니다. 스파 스 매트릭스를위한 특화된 패키지도 있으며, 밀도에 대해서는 확실하지 않습니다. – seberg
N은 미지수의 수 또는 행렬의 요소 수 (미지수의 제곱 수)입니까? – timday
NxN 행렬에 대한 DGESV의 시간 복잡도는 O (N^3)입니다. 다음 표 3.13을 참조하십시오. http://www.netlib.org/lapack/lug/node71.html –