기존 $O(N^3)$이 걸리는 가우스 소거법 알고리즘을 CUDA 프로그래밍을 통해 $O(N)$으로 단축하는 프로젝트이다.
이론적으로는 $O(N)$ 시간에 연산을 수행하지만 다음과 같은 요인 때문에 실제로는 더 느리다.

• 연산을 진행하는 도중에 GPU 코어의 할당 시간 존재
• 한 번에 할당할 수 있는 물리적인 GPU 코어 개수 한계

• 프로젝트 발표 PPT 파일 (병렬 프로젝트 발표 PPT)

• Cuda
• C++

CPU에서 가우스 소거법은 $0 \leq i < N$인 i에 대해 $(i, i)$의 원소를 다음과 같은 과정을 수행해야 한다.

• $i < j < N$인 j에 대해 $(j, i)$의 원소들을 기본행 연산을 통해 0으로 만들어줘야 한다.
• 이를 수행하려면, $(i, i)$를 기준으로 아래 (직사각형) 영에 대해 연산을 해줘야 한다.
• 이는 상한 $O(N^2)$ 연산이 걸린다고 할 수 있다.

따라서 가우스 소거법의 시간 복잡도는 $O(N^3)$이다.
(참고로, 가우스 소거법 이후에 역대입법 과정은 $O(N^2)$이 걸린다.)

GPU를 이용하면 가우스 소거법의 $(N^2)$에 해당하는 연산을 아래의 그림과 같이 (이론적으로는) 상수 시간 $O(1)$에 처리할 수 있다.

또한 역대입법 과정 또한 아래의 그림과 같이 $O(N^2)$에서 $O(N)$으로 줄일 수 있다.

• PPT 제작을 포함한 모든 부분을 맡아서 진행함.