모든 n차 정사각 불리언 행렬 사이의 효율적 이중 연속곱셈에 관한 연구

• 영문명: A Study on the Efficient Two Consecutive Multiplications of All n x n Boolean Matrices
• 발행기관: 한국자료분석학회
• 저자명: 한재일(Jae-Il Han)
• 간행물 정보: 『Journal of The Korean Data Analysis Society (JKDAS)』Vol.8 No.3, 1209~1220쪽, 전체 12쪽
• 주제분류: 자연과학 > 통계학
• 파일형태: PDF
• 발행일자: 2006.06.30

국문 초록

불리언 행렬은 다양한 분야에서 유용하게 사용되고 있으며 많은 연구가 수행되었다. D 클래스는 주어진 동치관계에 있는 n차 정사각 불리언 행렬의 집합으로 정의되며, 정의에 따른 D-클래스 계산은 다섯 개의 n차 정사각 불리언 행렬로 이루어진 모든 조합에 대해 불리언 행렬의 사중 연속곱셈을 수행할 것을 요구한다. 그러나 거의 모든 불리언 행렬에 대한 연구는 단지 두 불리언 행렬의 효율적 곱셈에 초점을 두고 있으며, D-클래스 계산과 같은 응용에서 필요한 모든 불리언 행렬 사이의 곱셈이나 연속곱셈에 대한 연구는 극히 소수만이 보이고 있다. 더구나 모든 불리언 행렬 사이의 연속곱셈에 대한 연구는 실행시간 개선이 매우 미흡하다. 본 논문은 하나의 n차 정사각 불리언 행렬과 모든 n차 정사각 불리언 행렬 사이의 이중 연속곱셈을 효율적으로 할 수 있는 이론을 제시하고, 이를 적용한 알고리즘을 기술한 후 실제 컴퓨터 실행결과로 얻은 데이터 분석을 통해 실행시간이 크게 개선되었음을 논한다.

영문 초록

Boolean matrices have been successfully used in various areas, and many researches have been performed on them. D-class is defined as a set of equivalent n x n boolean matrices according to a given equivalence relation, and its computation requires in its naive form four consecutive multiplications of five matrices for each of all possible quintuples of n x n boolean matrices . However, almost all the researches on boolean matrices focused on the efficient multiplication of only two boolean matrices and only a few researches have been shown to deal with the multiplication or consecutive multiplications of all boolean matrices that are needed for applications such as the D-class computation. Furthermore, the researches on the consecutive multiplications of all boolean matrices show very little improvement in execution time. The paper suggests a theory with which consecutively multiplying an n x n boolean matrix by all n x n boolean matrices can be done efficiently, describes algorithms designed with the theory, and shows big improvement in execution time by analyzing their execution results on a computer.

목차

1. 서론

2. 관련연구 및 문제점

3. n 차 정사각 불리언 행렬의 이중 연속곱셈

4. 이중 연속곱셈의 계산복잡도

5. 알고리즘 및 실행결과

6. 결론 및 향후 연구방향

참고문헌

키워드

불리언 행렬 행렬 곱셈 NP-완전 계산복잡도 Boolean Matrix Matrix Multiplication NP-Complete Computational Complexity