|
1. arithinva@trinitas.mju.ac.kr
의
목적 [ English
]
다음과 같은 Gaussian 다항식의
곱으로 이루어진 다항식의 모든 계수(arithmetic
invariant)를 계산하여
(*)
(1+t)^e(1)*(1+t+t^2)^e(2)*(1+t+t^2+t^3)^e(3)***(1+t+t^2+...+t^(n-1))^e(n)
그 결과를 전자메일로
보내 줌.
2. 소개
위의 수식 (*)에서 Gaussian polynomial,
1+t+t^2+...+t^(n-1) , 의 갯수가 증가하면,
이들의 곱인 위 다항식의 계수들을
계산하는 것이 매우 힘들어진다.
최근에, 소순태 교수는 multiset M 위에
정의 된 (graded) partition function의 값을
계산하는 두 개의 새로운 점화 공식
(absolute recursive formula 와 (quasi-) recursive
formula) 들을 발견하였는데, 이들 두
공식을 사용하여 우리는 수식 (*) 의
모든 계수를 효과적으로 계산할 수
있는 새로운 알고리즘을 갖게 되었다.
Soh's
algorithm for q-series for (*)
여기서는 이
알고리즘을 사용하여 위 수식 (*) 의
모든 계수들을 구한다. 다항식 곱에,
다음의 수식 (**) 과 같이, Gaussian
다항식의 중복이나 생략이 전혀 없을
때 (즉, 수식(*)에서 모든 e(i) 가 1 일
경우)
(**)
(1+t)*(1+t+t^2)*(1+t+t^2+t^3)***(1+t+t^2+...+t^(n-1)).
이 알고리즘의 Time efficiency
는 O(m^2) 이다. 단, 여기서 m 은 제일 첫
번째 계수인 1 부터 순차적으로
구하려고 하는 계수들의 총 갯수이다.
3. 기여자: 현재 사용 중인
프로그램은 명지대학교 수학과
소순태 교수가 Computer Algebra System (CAS)
인 Reduce를 사용하여 구축하였다.
4. Note
접수된 전자메일을 에러없이
처리하기 위하여, Microsoft 사의 Outlook
Express에서 New mail > Alt+O > Alt+X (with
No Encryption) 을 사용하여 arithinva@trinitas.mju.ac.kr
로 다음의 제 5항의 설명에 따라
작성한 전자메일을 보낼 것을 적극 권장한다.
5. 전자메일을
보내는 방법: 주어진 다항식이
(***) (1+t+t^2)^3*(1+t+t^2+t^3+t^4+t^5)^4*(1+t+t^2+t^3+t^4+t^5+t^6+t^7+t^8)^5
일 때, 본문이
input:
multiset:={3,3,3,6,6,6,6,9,9,9,9,9}$
f:=2$
end input:
으로 이루어진 plain-text
양식의 전자메일 (예를 들어, Microsoft
Outlook Express 일 경우에는 New mail > Alt+o
> Alt+x (with No Encryption)) 을 arithinva@trinitas.mju.ac.kr
로 보낸다. 그러면, 전자메일의 도착
즉시 input: 과 end input: 사이의 input에
근거하여 위의 수식 (*) 의 모든
계수를 계산하여 그
결과와 본 서버에서 전자메일로
요청한 전체 계산에 소요된 시간(timex
report)을 담은 전자메일을 즉시
송신자에게 발송함.
단, 위의 예제에서,
(i) 수식(***)에 있는 각 Gaussain polynomial
로 부터 필요로 하는 multiset은 다음과
같이 구해 진다.
1+t+t^2+t^3+...t^n-1 -> n
for each Gaussian polynomial in the product,
(ii) 첫 번째 줄에 있는, multiset:={3,3,3,6,6,6,6,9,9,9,9,9}$ , 은
다음의 줄로 대치할 수 있다:
multiset:={{3,3},{6,4},{9,5}}$
(iii) 2가 아닌 다른 자연수 값을 efficiency control
parameter 인 f >1 의 값으로 선택할 수 있다.
더구나, 메일의 본문에,
예를 들어,
input:
n:=10$
end input:
이라고 쓰면, 다음의
다항식을 전개한 다항식의 모든
계수를 계산하게 된다:
(1+t)*(1+t+t^2)***(1+t+t^2+...+t^(10-1))
단, 이 때 f > 1 의
최적값은 다음의 Note에 있는 공식에
의하여 자동적으로 선정되게 하는
것이 좋다.
Note 1: 매우
복잡하거나 큰 multiset의 경우에는,
다음의 공식에 따라 2가 아닌 다른
자연수를 f > 1 의 값으로 택할 수
있다:
f:=[exp(sqrt( ln(2)*ln(N) ))]$
여기서, [m] 은 Gaussian
integer 함수이고 N 은 선택한 multiset의
크기이다.
[참고: 대개의 경우, 즉
multiset이 상당히 크지 않는 한, f:=2$ 로
택하는 것이 효율적인 경우가 많다.]
Note 2: 그리고, f > 1 의 값을
위의 예제에서와 같이 구체적으로
택하여 주지 않으면 위의 Note 1 에
있는 공식에 의하여 f의 값이 자동적으로
선정된다.
[주의] 복잡하지
않은 계산을 위 전자메일 주소로
의뢰하였을 경우에는 대개 3 - 4 분
이내에 결과를 받아 볼 수
있습니다. 그러나, 의뢰한 계산을
수행한 후 그 계산결과를 답신으로서
송신자에게 보내 드렸으나, (i)
송신자의 주소가 틀리거나 (ii) 혹은
송신자의 전자메일 통이 다른
전자메일로 가득 차 있어, 송신자
측에 제대로 접수가 되지 않고 되돌아
오는 경우가 간혹 있으니, 위의 제 5항의
전자메일 주소로 계산을 의뢰한 후
일정시간 이상 기다려도 답신이 없을
경우에는, 본인의 메일계정의 상태를
점검하여 위의 (i) 과 (ii)의 문제를
해결한 후 다시 한 번 위의 제 5항과
같이 전자메일을 보내 주시면
되겠습니다.
|
