[알고리즘] 다중격자 알고리즘 (Multigrid algorithm)

 

 

경제적, 정치적 결정을 내릴 때 시뮬레이션을 참고하는 경향은 오늘 날 점점 강화되고 있습니다. 현실에서 일어나는 과정을 컴퓨터에서 계산 하는 것인데 그 이유는 2가지가 있습니다.

 

 

첫째, 아직 일어난 적 없는 과정을 연구할 때 시뮬레이션이 쓰입니다. 날씨 예측이나 향후 100년 동안의 세계 기후 시뮬레이션들 일어나지 않은 과정들에 활용이 됩니다.

 

둘째, 현실에서 실험이 너무 번거롭거나 비용이 많이 들 때 시뮬레이션이 쓰입니다. 예컨데 현실에서자동차 충돌 실험을 하려면 매번 비싼 차체를 고철로 만들어야 합니다. 충돌 과정 전체를 컴퓨터에서 계산할 수 있다면 효율적으로 일을 해결할 수 있습니다.

 

하지만 위의 2가지 이유말고 의문점이 생깁니다. "여기서 말하는 시뮬레이션은 현실과 얼마나 유사할까?" 라는 질문을 할 수 있습니다. 왜냐하면 시뮬레이션은 엄연치 현실과는 오차범위가 있고 언제나 예외,변수등이 일어날 수 있습니다.

 

현실에서 마주치는 과정을 계산하려며 물리량들의 상호관계를 기술하는 '미분방정식'을 풀어야 합니다. 그런데 대개의 미분방정식 풀이는 완전한 해를 구하는 방식으로 이루어지지 않습니다. 대신에 사람들은 문제를 모든 점에서 고찰하지 않고 띄엄띄엄 떨어진 점들로 구성된 격자에서만 고찰함으로써 이산화 (discretize)합니다. 예를 들어 온도, 풍속 등을 모든 지점에서 계산하는 대신에 전체 지역을 1제곱 킬로미터 면적의 구역으로 나누고 각 구역에서의 값을 계산하는 것으로 만족해야 합니다.

 

일반적으로 그 격자가 촘촘할수록 미분방정식의 해는 현실과 더 유사하게 됩니다. 그러나 격자가 촘촘해지면 그만큼 계산에 공이 더 많이듭니다. 이를테면 3차원 공간에서 일어나는 한 현상을 시뮬레이션하는데, 격자의 눈의 한 변을 반으로 줄이면 계산에서 고려할 점들이 8배로 늘어나므로 계산 시간도 8배로 늘어나게 됩니다. 이 때문에 날씨 예측에서 격자를 점점 더 촘촘하게 만들다보면 내일 날씨의 계산 결과가 모래에야 나오는 상황이 발생할 수도 있습니다.

 

 

 

때로는 촘촘한 격자가 필요하지 않습니다. 예컨대 기체나 액체의 흐름을 고찰할 때는 그 흐름이 층류(laminar flow)여서 뒤엉킴 없이 매끄럽게 흐르기만 한다면 비교적 성긴 격자로도 좋은 계산 결과를얻을 수 있습니다. 반면에 난류(turbulent flow)에서는 아주 작은 소용돌이 하나도 흐름 전체에 중요한 영향을 미치므로 더 촘촘한 격자가 필요합니다.

 

이른바 '다중격자 알고리즘(multigrid algorithm)'의 원리는 1970년대 후반 이래로 개발되었습니다. 이 알고리즘은 고정된 격자를 사용하는 대신에 풀어야 할 미분 방정식을 고찰하여 어느 구역에서는 격자를 더 촘촘하게 만들어야 하고 어느 구역에서는 비교적 성긴 격자로도 충분한지 판단합니다. 이 알고리즘의 최대 장점은 계산의 복잡성을 줄여서 훨씬 더 빠른 계산을 가능케 하는 것에 있습니다.

 

다중격자 알고리즘은 최신 컴퓨터들의 계산 능력 향상에도 불구하고 그 능력을 아껴 쓰기 위한 노력이 앞으로도 늘 필요할 것임을 보여주는 한 사례입니다. 오늘날 사람들은 컴퓨터의 놀라운 성능을 대수롭지 않게 여기는 경우가 많습니다. 컴퓨터 내부에서 작동하는 알고리즘의 효율성을 높이기 위해서 수많은 노력과 인력이 들어갑니다.

 

 

#다중격자알고리즘 #multigridalgorithm