본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

관측행렬에 대한 전처리 Cholesky-Factor Downdating 기법
Preprocessed Cholesky-Factor Downdatings for Observation Matrices

김석일   (충북대학교 컴퓨터과학과  ); 이충한   (충북대학교 컴퓨터과학과  ); 전중남   (충북대학교 컴퓨터과학과  );
  • 초록

    본 논문에서는 다행관측행렬 Z $^T$ 를 빠르게 downdating하기 위하여 Z $^T$ 의 partial Cholesky factor Rz를 계산하는 전처리 과전을 거친 후, RZ에 각각 기존의 GD(Givens Downdting)기법과 HD(Hyperbolic Downdating)기법을 적용한 PGD(Preprocessed GD)기법 과 PHD(Preprocessed HD)기법을 제안하였다. p $\times$ n(p $\geq$ n)크기의 다행관측행렬 ZT를 downdating 하는 데필요한 시간복잡도는 PGD 및 PHD기법을 이용한downdating의 경우 에 각각 $pn^2$ + $5n^3/6$ 및 $pn^2$ + $n^3/3$ flops이며, 기존의GD기법또는 HD기법을이용한 downdating에서는 각각 5np2/2 과 2np2 flops이므로 다행관측행렬 Z $^T$ 를 partial Cholesky factor RTZ로 분할하는 전처리 과정이 downdating알고리즘의 성능을 개선할 수 있음을 보여준다. Sun SPARC/2 시스템에서의 벤치 마크 실험 결과도 전처리 과정을 거친 알고리즘의 실행 속도가 전 처리 과정을 거치지 않은 알고리즘에 비하여 빠른 결과 를 얻었으며, 두가지 전처리 기법 중에서도 PHD 기법이 PGD기법 보다 시간복잡도 측면 에서 우수하였다.


    This paper introduces PGD(Preprocessed Givens Downdating)and PHD(Preprocessed Hyperbolic Downdating) algorithms, wherein a multiple-row observation matrix $Z^T$ is factorized into a partial Cholesky factor Rz, such that $Z^T$ = <TE $Q_zR_z, Q_zQ^T_z=I$ , and then Rz is recursively downdated by using GD(Givens Downdating)and HD(Hyperbolic Dondating), respectively. Time complexities of PGD and PHD algorithms are $pn^2$ + $5n^3/6$ 및 $pn^2$ + $n^3/3$ flops, respectively, if p $\geq$ n, while those of the existing GD and HD are known to be $5pn^2/2$ and $2pn^2$ flops,, respectively. This concludes that the factorization of observation matrices, which we call preprocessing, would improve the overall performance of the downdating process. Benchmarks on the Sun SPARC/2 system also show that preprocessing would shorten the required downdating times compared to those of downdatings without preprocessing. Furthermore, benchmarks also show that PHD provides better performance than PGD.


 저자의 다른 논문

  • 김석일 (26)

    1. 1994 "PALM시스템의 구조와 네트웍 성능" 정보처리논문지 = The transactions of the Korea Information Processing Society 1 (1): 105~113    
    2. 1994 "병렬처리 컴퓨터의 특징과 처리기법" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 12 (5): 39~53    
    3. 1995 "Multiple-Row Downdating을 수행하는 고속 최소자승 알고리즘" 정보처리논문지 = The transactions of the Korea Information Processing Society 2 (1): 55~65    
    4. 1997 "클라이언트/서버 환경과 컴퓨팅 모델" 정보처리학회지 = Korea information processing society review 4 (6): 4~15    
    5. 1997 "목적 코드에서 LNOP 코드가 제거됨에 따른 SVLIW 구조의 성능 향상" 정보처리논문지 = The transactions of the Korea Information Processing Society 4 (9): 2269~2279    
    6. 1997 "SVLIW 프로세서와 VLIW 프로세서의 명령어 캐싱에 따른 성능 분석" 전기전자학회논문지 = Journal of IKEEE 1 (1): 101~110    
    7. 1998 "자동 역점역을 가능하게 하는 한글점자 부호체계의 개선" 정보처리논문지 = The transactions of the Korea Information Processing Society 5 (3): 703~714    
    8. 1998 "통신의 영향을 줄이기 위한 이기종 태스크 스케쥴링 기법" 정보처리논문지 = The transactions of the Korea Information Processing Society 5 (10): 2521~2532    
    9. 1999 "루프를 효과적으로 처리하는 PASC 프로세서 구조" 정보처리논문지 = The transactions of the Korea Information Processing Society 6 (5): 1225~1240    
    10. 1999 "클러스터링을 이용한 경험적 태스크 할당 기법" 정보처리논문지 = The transactions of the Korea Information Processing Society 6 (10): 2659~2669    
  • 이충한 (2)

  • 전중남 (27)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기