데이터처리 알고리즘의 재해석

전문가 제언

이 논문은 UC Berkeley의 통계학과와 국제 컴퓨터과학협회에 종사하는 겸임부교수 Michael W. Mahoney가 COMMUNICATIONS OF THE ACM의 연구하이라이트 난에 기고한 글로, TCS 분야에서 데이터처리의 관심사와 동향을 언급하고 데이터 통신과 계산의 Trade-off를 고려한 새로운 알고리즘에 대한 소개와 시사점을 요약 제시한다.

 

이론과 실제상 지나 수년간 지배적이었던 매트릭스 알고리즘기반의 구 알고리즘과 대비되는 새로운 알고리즘을 채택하는데 있어, 근본적인 문제를 고려하는 논문이 Ballard, Demmel, Holtz, Schwartz 등에 의해 제시되었다. 논문은 이론적 컴퓨터과학(TCS)에서의 추상적 아이디어가 실제로 어떻게 유용한 결과를 낼 수 있을지를 강조하고, 이론과 실제의 차이에 대한 연결을 어떻게 이해시킬지를 설명한다.

 

결론적으로 저자는 최적 알고리즘에 의한 타이트한 하한을 보여준다고 주장한다. 순차적인 경우는 Strassen 알고리즘의 표준적 실행으로 달성되며, 병렬적인 경우의 적용을 위해 저자는 Benjamin Lipshitz와 공동 작업으로 '통신회피(Comm unication Avoiding)적 병렬 Strassen 알고리즘'을 개발했다. 개발된 알고리즘은 앞서의 두 알고리즘(3-loop, Strasen)보다 덜 점근적(asymptotically)으로 통신하며, 성능도 알려진 매트릭스 연산알고리즘이나 3-loop 및 Strassen 알고리즘보다 좋게 나타난다고 언급한다. 그러나

아이러니컬하게도 Strassen 알고리즘이 여전히 실질적인 것으로 보인다고 제안하고 있다. 연구가 필요한 부분이다.

저자

Michael W. Mahoney

자료유형

연구단신

원문언어

영어

기업산업분류

정보통신

연도

2014

권(호)

57(2)

잡지명

Communications of the acm

과학기술
표준분류

정보통신

페이지

106~106

분석자

박*만

분석물

• 데이터처리 알고리즘의 재해석.pdf [240,339 byte]

이미지변환중입니다.