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

A Study on the Efficient Two Consecutive Multiplications of All n x n Boolean Matrices

불리언 행렬은 다양한 분야에서 유용하게 사용되고 있으며 많은 연구가 수행되었다. 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.