3x3 Matrix Multiplication에 대한 더 효율적인 Algorithm 개발

From Course@DGIST
Revision as of 12:44, 11 November 2019 by Kjhan (talk | contribs) (과제 내용)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
3x3 Matrix Multiplication에 대한 더 효율적인 Algorithm 개발
제안자 한강진
자문교원 한강진
연도 2020
타입 A형 과제
코스 프란시스 크릭
매칭여부 No
참여학생수
소개동영상

제안 배경

우리가 고등학교때 (안타깝게도 현재는 안 배운다) 배운 행렬에 대해 생각해 보면, 같은 크기의 두 행렬의 덧셈은 성분별로(componentwisely)하고 매우 자연스러워 보이나, 두 행렬의 곱셈을 처음 볼때 '왜 이렇게 하지?' 어색한 생각이 들었던 기억이 있을 것이다. 예를 들어, 두 개의 2x2 행렬을 곱할때, "덧셈 4번" "곱셈 8번"을 사용해 우리는 계산한다.

1960년대 중반 V. Strassen은 이런 계산법이 가장 효율적(effective)임을 보이고 싶었으나, 끝내 그는 조금 '특이한' 그만의 2x2 행렬 곱셈방법을 개발하는 결과를 얻었다 - "덧셈은 18번" "곱셈 7번" 사용하는 Strassen's algorithm for Matrix Multiplication. 무슨 결과인가? 할 수 있지만, 거대한 행렬의 곱셈을 계산할 때, 2x2 iteration으로 곱셈을 수행할 경우 standard algorithm보다 훨씬 계산량이 적은 (low computational cost)결과를 얻게 됨을 알게 되었다. 그리고 2005년 J. Landsberg에 의해 '7번 곱셈을 사용하는 계산법이 2x2행렬의 경우 최소 곱셈횟수 방법이라'는 것이 증명되었다.

자연스럽게 3x3 행렬에 대한 곱셈을 생각할 수 있고, 이 문제에 대한 최적값은 still open! 모두에게 열려있다. 이번 UGRP를 통해 이 문제에 도전하여 보자 (note : 자연스러운 알고리즘은 곱셈을 3^3=27번 사용하게 되고, 70년대 23번, 80년대 22번 사용하는 알고리즘이 제안되었다. 그러나 여전히 이것이 최적인지는 모른다).

과제 목표

  • 3x3 행렬 곱셈에 있어서, 곱셈의 횟수를 기존 제안 방법보다 줄이는 algorithm을 개발하고, 가능하다면 최적의 횟수를 갖는 방법을 찾는다.
  • 관련하여, 선형대수학의 행렬의 자연스러운 고차원 확장(high dimensional analogue)인 텐서(tensor)에 대한 기본 개념과 성질을 익힌다.
  • 새롭게 제안된 행렬곱 텐서의 계산법을 적용할 수 있는 Application을 Computation theory, Computer science, Signal Processing 등의 영역에서 찾아본다.

과제 내용

  • (다중)입력에 대한 출력이 선형(multi-linear)인 모든 공식(formula), 알고리즘(algorithm), 과정(process)는 모두 수학적으로 볼때 텐서(tensor)의 개념으로 이해할 수 있음을 익힌다.
  • 관심있는 알고리즘들이 이루는 공간(space)이 매우 흥미로운 기하학적 대상(geometric object)이 될 수 있음을 학습한다.
  • 이에 기반한 기하학적 관점과 (다중)선형대수학적 계산을 행렬곱과 알고리즘 공간에 함께 적용하며, 서로 다른 관점에 대한 상호연관성을 이해하고 구체적으로 계산을 진행하는 시간을 가진다.
  • 향후 연구자로서 필요한 paper reading과 seminar presentation을 UGRP 과정동안 진행하며 해당능력을 향상한다.
  • 연구주제가 매우 구체적인 까닭에 제안되고 토의된 아이디어에 대한 각자 가능한 언어로(C++, Python, Matlab, Macaulay2 등) coding을 진행하고, Experimental Mathematics의 가능성과 효용성에 대한 시야를 확보하는 경험을 갖도록 한다.

참고자료

  • J.M.Landsberg : 2000년대 초 2x2 행렬 곱에서 7번 곱셈이 최적 값인 것을 증명한 논문
  • J.D. Laderman : 1970년대 3x3 행렬 곱을 23번 곱셈을 사용하여 계산하는 방법을 제안한 논문
  • O.M. Makarov : 1980년대 22번 곱셈을 사용하여 같은 계산을 얻을 수 있는 방법을 제안한 논문
  • (Youtube) Strassen 알고리즘과 이를 큰 행렬곱에 iteratively 적용하는 것에 대한 설명 (22min)

희망학생