모든 m$\times$k 불리언 행렬과의 효율적 곱셈에 관한 연구

한재일,Han, Jae-Il 한국콘텐츠학회 2006 한국콘텐츠학회논문지 Vol.6 No.2

불리언 행렬은 다양한 분야에 응용되어 유용하게 사용되고 있으며 불리언 행렬에 대한 많은 연구가 수행되었다 대부분의 연구에서는 불리언 행렬의 곱셈을 다루고 있으나 모두 두 불리언 행렬 사이의 곱셈에 관심을 두고 있으며 다수의 n$\times$m 불리언 행렬과 모든 m$\times$k불리언 행렬 사이의 곱셈은 극히 소수의 연구에서 보이고 있다. 본 논문은 기존에 제시된 두 불리언 행렬의 최적 곱셈 알고리즘이 모든 불리언행렬에 대한 곱셈을 해야 하는 경우 부적합함을 보이고 n$\times$m 불리언 행렬과 모든 m$\times$k 불리언 행렬의 곱셈을 효율적으로 계산할 수 있는 이론을 정립한 후 이를 적용한 불리언 행렬 곱셈의 실행결과에 대하여 논한다. Boolean matrices are applied to a variety of areas and used successfully in many applications, and there are many researches on boolean matrices. Most researches deal with the multiplication of boolean matrices, but all of them focus on the multiplication of two boolean matrices and very few researches deal with the multiplication between many n$\times$m boolean matrices and all m$\times$k boolean matrices. The paper discusses the existing optimal algorithms for the multiplication of two boolean matrices are not suitable for the multiplication between a n$\times$m boolean matrix and all m$\times$k boolean matrices, establishes a theory that enables the efficient multiplication of a n$\times$m boolean matrix and all m$\times$k boolean matrices, and shows the execution results of a multiplication algorithm designed with this theory.

불리언 행렬의 곱셈에 관한 연구

한재일(Han Jae-Il),전성택(Jun Sung-Taeg) 한국콘텐츠학회 2005 한국콘텐츠학회 종합학술대회 논문집 Vol.3 No.2

불리언 행렬은 다양한 분야에 응용되어 유용하게 사용되고 있으며, 불리언 행렬의 응용과 곱셈에 대하여 많은 연구가 수행되었다. 대부분의 연구에서는 불리언 행렬의 곱셈을 다루고 있으나 모두 두 불리언 행렬 곱셈에 관심을 두고 있으며 많은 불리언 행렬 쌍의 곱셈은 극히 소수의 연구에서 보이고 있다. 본 논문에서는 기존에 제시된 두 불리언 행렬의 최적 곱셈 알고리즘이 많은 불리언 행렬 쌍에 대한 곱셈을 해야 하는 경우 부적합함을 보이고 하나의 n×m 불리언 행렬과 모든 m×k 불리언 행렬의 곱셈을 개선시킬 수 있는 방법을 제시한다. Boolean matrices are applied to a variety of areas and used successfully in many applications. There are many researches on the application and multiplication of boolean matrices. Most researches deal with the multiplication of boolean matrices, but all of them focus on the multiplication of just two boolean matrices and very few researches deal with the multiplication of many pairs of two boolean matrices. The paper discusses it is not suitable to use for the multiplication of many pairs of two boolean matrices the algorithm for the multiplication of two boolean matrices that is considered optimal up to now, and suggests a method that can improve the multiplication of a n×m boolean matrix and all m×k boolean matrices.

모든 n 차 정사각 불리언 행렬 쌍에 대한 벡터 기반의 곱셈 알고리즘

한재일 ( Jae-il Han ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.2

일반 행렬이나 불리언 행렬의 연산에 대한 많은 연구가 있다. 대부분의 연구는 두 행렬의 효율적 곱셈을 다루고 있으며 하드웨어나 소프트웨어적 응용에 적합한 다양한 알고리즘을 제시하였다. 모든 행렬 쌍의 곱셈에 대한 연구는 NP-완전 계산 복잡도와 이러한 곱셈을 요구하는 응용의 희소성으로 인해 관심밖에 있었으며 최근에야 원소가 불리언 값을 가지는 n 차 정사각 불리언 행렬을 대상으로 기초적인 연구 결과를 보이고 있다. 본 논문은 모든 n 차 정사각 불리언 행렬 사이의 곱셈을 보다 효율적으로 할 수 있는 벡터 기반 불리언 행렬 곱셈 이론과 이를 바탕으로 설계한 알고리즘 그리고 실행 결과에 대하여 논한다.

효율적인 D-클래스 계산을 위한 알고리즘

한재일(Jae-Il Han) 한국IT서비스학회 2007 한국IT서비스학회지 Vol.6 No.1

  D-class computation requires multiplication of three Boolean matrices for each of all possible triples of n×n Boolean matrices and search for equivalent n×n Boolean matrices according to a specific equivalence relation. It is easy to see that even multiplying all n×n Boolean matrices with themselves shows exponential time complexity and D-Class computation was left an unsolved problem due to its computational complexity. The vector-based multiplication theory shows that the multiplication of three Boolean matrices for each of all possible triples of n×n Boolean matrices can be done much more efficiently. However, D-Class computation requires computation of equivalent classes in addition to the efficient multiplication. The paper discusses a theory and an algorithm for efficient D-class computation, and shows execution results of the algorithm.

모든 l × n, n × m, m × k 불리언 행렬의 곱셈 시간 개선에 관한 연구

한재일 ( Jae-il Han ) 한국정보처리학회 2006 한국정보처리학회 학술대회논문집 Vol.13 No.1

대부분의 불리언 행렬에 대한 연구는 두 불리언 행렬의 곱셈에 초점을 두고 있으며 모든 불리언 행렬을 대상으로 한 곱셈에 대한 연구는 최근에야 극히 소수의 연구결과가 보이고 있다. 이 연구들은 모든 불리언 행렬 사이의 곱셈 실행시간을 개선시켰으나 연속된 세 개의 모든 l × n, n × m, m × k 불리언 행렬에 대한 곱셈은 아직 많은 개선이 필요하다. 본 논문은 모든 l × n, n × m, m × k 불리언행렬의 곱셈 실행시간을 보다 개선할 수 있는 이론을 제시하고 이를 적용한 불리언 행렬 연속곱셈의 실행결과에 대하여 논한다.

D-클래스 계산을 위한 불리언 행렬의 효율적 곱셈 및 알고리즘

한재일(Jae-Il Han),신범주(Bum-Joo Shin) 한국산업정보학회 2007 한국산업정보학회논문지 Vol.12 No.2

대규모 셀룰러 병렬 처리기의 재구현에 대한 수학적 정의와 계산 복잡도

한재일(Jae-Il Han) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.2

초대규모 집적(Very Large Scale Integration) 또는 웨이퍼규모 집적(Wafer Scale Integration)을 이용한 대규모 셀룰러 병렬 처리기(Large Scale Cellular Array Processor)들은 병렬 컴퓨터의 중요한 한 부류로 하나의 칩이나 웨이퍼에 단지 이웃으로만 연결된 많은 수의 단순 구조를 가지는 처리기로 구성 된다. 이런 셀룰러 병렬 처리기들에 있어 재구현(Reconfiguration)은 중요한 근본적인 문제로 결함 허용 재구현(Fault-Tolerant Reconfiguration), 기능적 재구현(Functional Reconfiguration), 그리고 통합 재구현(Integrated Reconfiguration)의 세가지 형태가 있다. 재구현 과정에 있어 필수적인 구성(Configuration)단계는 그 중요성에도 불구하고 이에 대한 명확한 정의가 내려져 있지 않다. 또한 통합 재구현은 최근에야 언급 된 문제로서 아직 어떤 연구가 되어 있지 않은 상태이다. 본 논문은 부그래프 준동형성(Subgraph Homeomorphism)을 통해 세가지 재구현의 구성단계를 명확히 쟁의하고, 각 구성단계의 관계를 밝혔으며, 통합 재구현에서는 각 구성단계의 차이점이 단지 개념적임을 보였다. 또한 본 논문에서는 각 재구현 과정의 계산 복잡도와 통합 재구현 과정에서 핵심적 역활을 하는 두개의 사상(Mapping)을 보였다. One important class of highly parallel computers includes the large scale cellular array processors that are built with VLSI (Very Large Scale Integration) or WSI (Wafer Scale Integration) technologies. Those cellular array processors consist of a large number of simple processing cells, all on a single chip or wafer, each interconnected only to its neighbors. The fundamental issues in those cellular array processors are fault-tolerant reconfiguration, functional reconfiguration, and their integration. Although configuration is an essential task in the reconfiguration process, no one has given its precise and formal definition properly. The issue of integrating fault-tolerant reconfiguration and functional reconfiguration has been addressed only recently, and to the best of the author's knowledge, no significant study has been done on that problem. This paper characterizes the configuration tasks in terms of subgraph homeomorphism, identifies the relation between them, and shows that any difference between them is only conceptual in integrated reconfiguration. Then, the paper discusses the computational complexity of each reconfiguration process, and shows two mappings that play a key role in the integrated reconfiguration process.

하나의 n 차 정사각 불리언 행렬과 모든 n 차 정사각 불리언 행렬 사이의 연속곱셈에 관한 연구

한재일(Han Jae-Il) 한국콘텐츠학회 2006 한국콘텐츠학회 종합학술대회 논문집 Vol.4 No.1

모든 n차 정사각 불리언 행렬 사이의 연속곱셈은 D-클래스 계산과 같은 응용에서 기본적으로 요구되는 연산이다. 그러나 불리언 행렬에 대한 많은 연구에도 불구하고 이에 대한 연구는 아직 보이지 않고 있다. 본 논문은 하나의 n차 정사각 불리언 행렬과 모든 n차 정사각 불리언 행렬 사이의 이중 연속곱셈을 효율적으로 할 수 있는 이론을 제시하고, 이를 모든 n차 정사각 불리언 행렬 사이의 연속곱셈에 적용한 실행결과를 보인다. The successive multiplication of all n × n boolean matrices is necessary for applications such as D-class computation. But, no research has been performed on it despite many researches dealing with boolean matrices. The paper suggests a theory with which successively multiplying a n × n boolean matrix by all n × n boolean matrices can be done efficiently, applies it to the successive multiplication of all n × n boolean matrices and shows its execution results.

6LoWPAN에서 단편화 관리기법

한재일(Han Jae Il),서현곤(Seo Hyun Gon) 한국통신학회 2008 한국통신학회 학술대회논문집 Vol.2008 No.7

모든 l×n, n×m, m×k 불리언 행렬 사이의 중첩곱셈에 대한 연구

한재일(Jae-Il Han) 한국IT서비스학회 2006 한국IT서비스학회지 Vol.5 No.1

  Boolean matrices have been successfully used in various areas, and many researches have been performed on them. However, almost all the researches focus on the efficient multiplication of two boolean matrices and no research has been shown to deal with the multiplication of all boolean matrices and their consecutive multiplications. The paper suggests a mathematical theory that enables the efficient consecutive multiplications of all l×n , n×m , and m×k boolean matrices, and discusses its computational complexity and the execution results of the consecutive multiplication algorithm based on the theory.