문서에서의 구문적 오류 검출

김진우,마상백,김한우 漢陽大學校 工學技術硏究所 1999 工學技術論文集 Vol.8 No.1

본 논문은 기존의 철자 검사기로는 검출해 내지 못했던 구문 오류 일부를 검출해 낼 있는 방법을 제시한다. 일반적으로 문서작업을 할 때의 오타입력은 주로 자판 입력시 주위 문자를 잘못 입력하는 경우의 오류가 대부분이다. 이러한 오류 단어가 형태소 분석에 실패하는 경우는 철자 오류검사로도 교정이 되지만 형태소 분석을 성공한 경우에는 검출이 불가능하다. 따라서 형태소 분석을 통과한 오류 단어를 발견하는 방법을 제안한다. 이 방법은 특정 단어를 자소 대치를 한 후 다른 단어와 비교하여 오류일 확률이 낮은 단어와 매칭이 된다면 일단 오류 후보로 가정한다는 것이다. 여기에는 일부 휴리스틱한 제약이 필요하다. 이 단어간 비교에 의한 추정은 전에 발견하지 못했던 구문 오류 일부를 발견할 수 있게 해준다. In a typed document, spelling errors are cause of word errors. Traditional Critiquing system like a spelling checker detects spelling error using a morphological analyser. If morphological analyser detected a certain error word, it could also correct the error word. In other case, spelling checker can not detect a error word. In this paper, a method that can detect additional syntactic errors by comparing words in a document is proposed. The method is based on word errors appearing frequently in typist's misspelling using word processor. In this the method, a certain word is changed by one-letter substitution, and the changed word is compared with errors of low possibility words in a document. If the changed word matches errors of low possibility words, this method deduces that the word is the error of high possibility word. The method has to be added with various heuristic restrictions. The Deduction Using Words Comparison' method can detect additional syntactic errors.

AN ASSESSMENT OF PARALLEL PRECONDITIONERS FOR THE INTERIOR SPARSE GENERALIZED EIGENVALUE PROBLEMS BY CG-TYPE METHODS ON AN IBM REGATTA MACHINE

Ma, Sang-Back,Jang, Ho-Jong 한국전산응용수학회 2007 Journal of applied mathematics & informatics Vol.25 No.1

Computing the interior spectrum of large sparse generalized eigenvalue problems $Ax\;=\;{\lambda}Bx$, where A and b are large sparse and SPD(Symmetric Positive Definite), is often required in areas such as structural mechanics and quantum chemistry, to name a few. Recently, CG-type methods have been found useful and hence, very amenable to parallel computation for very large problems. Also, as in the case of linear systems proper choice of preconditioning is known to accelerate the rate of convergence. After the smallest eigenpair is found we use the orthogonal deflation technique to find the next m-1 eigenvalues, which is also suitable for parallelization. This offers advantages over Jacobi-Davidson methods with partial shifts, which requires re-computation of preconditioner matrx with new shifts. We consider as preconditioners Incomplete LU(ILU)(0) in two variants, ever-relaxation(SOR), and Point-symmetric SOR(SSOR). We set m to be 5. We conducted our experiments on matrices from discretizations of partial differential equations by finite difference method. The generated matrices has dimensions up to 4 million and total number of processors are 32. MPI(Message Passing Interface) library was used for interprocessor communications. Our results show that in general the Multi-Color ILU(0) gives the best performance.

A partial proof of the convergence of the block-ADI preconditioner

Ma, Sang-Back Korean Mathematical Society 1996 대한수학회논문집 Vol.11 No.2

There is currently a regain of interest in ADI (Alternating Direction Implicit) method as a preconditioner for iterative Method for solving large sparse linear systems, because of its suitability for parallel computation. However the classical ADI is not applicable to FE(Finite Element) matrices. In this paper wer propose a Block-ADI method, which is applicable to Finite Element metrices. The new approach is a combination of classical ADI method and domain decompositi on. Also, we provide a partial proof of the convergence based on the results from the regular splittings, in case the discretization metrix is symmetric positive definite.

OPTIMAL $$\rho$$ PARAMETER FOR THE ADI ITERATION FOR THE SEPARABLE DIFFUSION EQUATION IN THREE DIMENSIONS

Ma, Sang-Back Korean Mathematical Society 1995 대한수학회논문집 Vol.10 No.1

The ADI method was introduced by Peaceman and Rachford [6] in 1955, to solve the discretized boundary value problems for elliptic and parabolic PDEs. The finite difference discretization of the model elliptic problem $$ (1) -\Delta u = f, \Omega = [0, 1] \times [0, 1] $$ $$ u = 0 on \delta \Omega $$ with 5-point centered finite difference discretization, with n +2 mesh-points in the x - direction and m + 2 points in the y direction, leads to the solution of a linear system of equations of the form $$ (2) Au = b $$ where A is a matrix of dimension $N = n \times m$. Without loss of generality and for the sake of simplicity, we will assume for the remainder of this paper that m = n, so that $N = n^2$.

COMPARISONS OF PARALLEL PRECONDITIONERS FOR THE COMPUTATION OF SMALLEST GENERALIZED EIGENVALUE

Ma, Sang-Back,Jang, Ho-Jong,Cho, Jae-Young 한국전산응용수학회 2003 Journal of applied mathematics & informatics Vol.11 No.1

Recently, an iterative algorithm for finding the interior eigenvalues of a definite matrix by CG-type method has been proposed. This method compares to the inverse power method. The given matrices A, and B are assumed to be large and sparse, and SPD( Symmetric Positive Definite) The CG scheme for the optimization of the Rayleigh quotient has been proven a very attractive and promising technique for large sparse eigenproblems for smallest eigenvalue. Also, it is very amenable to parallel computations, like the CG method for the linear systems. A proper choice of the preconditioner significantly improves the convergence of the CG scheme. But for parallel computations we need to find an efficient parallel preconditioner. Our candidates we ILU(0) in the wave-front order, ILU(0) in the multi-coloring order, Point-SSOR(Symmetric Successive Overrelaxation), and Multi-Color Block SSOR preconditioner. Wavefront order is a simple way to increase parallelism in the natural order, and Multi-coloring realizes a parallelism of order(N), where N is the order of the matrix. Another choice is the Multi-Color Block SSOR(Symmetric Successive OverRelaxation) preconditioning. Block SSOR is a symmetric preconditioner which is expected to minimize the interprocessor communication due to the blocking. We implemented the results on the CRAY-T3E with 128 nodes. The MPI (Message Passing Interface) library was adopted for the interprocessor communications. The test problem was drawn from the discretizations of partial differential equations by finite difference methods. The results show that for small number of processors Multi-Color ILU(0) has the best performance, while for large number of processors Multi-Color Block SSOR performs the best.

Parallel solution of linear systems on the CRAY-2 using micro tasking library

Ma, Sang-Back 漢陽大學校 工學技術硏究所 1997 工學技術論文集 Vol.6 No.1

CRAY 에서 마이크로 태스킹은 다수의 CPU를 이용하여 계산속도를 증가시키는 하나의 방법이다. CRAY-2 에는 4개의 CPU 가 있으므로 적절히 설계된 알고리즘을 가지고 최대 4배의 speedup을 실현할 수 있다. 저자는 이 논문에서 CRAY-2에서 마이크로태스킹 라이브러리를 이용한 선형시스템의 해의 병렬화를 제시한다. 문제의 알고리듬은 Radicati di Brozolo 가 제안한 준비행렬을 이용한 대형이산 행렬의 반복적 해법이다. 우리는 크기가 8192인 행렬에서 4개의 CPU에 마이크로 태스킹을 사용하여 3이상의 speedup을 얻었다. Radicati 의 테크닉을 혼합한 ILU(0) 준비행렬은 4개의 프로세서에서 상당히 높은 speedup을 얻었다. Multitasking and microtasking on the CRAY machine provides still another way to improve computational power. Since CRAY-2 has 4 processors we can achieve speedup up to 4 with properly designed algorithms. In this paper we present a parallelization of linear system solution un the CRAY-2 with the microtasking library. Our algorithm is the iterative solution of large sparse linear systems with the preconditioner proposed by Radicati di Brozolo. We were able to obtain a speedup of around 3 with 4 processors for a matrix of dimension 8192 with the microtasking. The ILU(0) preconditioner with Radicati's technique seem to realize a reasonably high speedup with 4 processors.

컴퓨터구조 : 대형이산 행렬 시스템의 초대형병렬컴퓨터에서의 해법을 위한 병렬준비 행렬의 비교

마상백(Ma Sang Back) 한국정보처리학회 1995 정보처리학회논문지 Vol.2 No.4

이 논문에서 우리는 CM-5와 같은 초대형병렬컴퓨터에서 대형 이산선형체제를 풀기 위한 준비행렬로써 두 가지를 소개한다. 대다수의 초대형병렬컴퓨터들은 프로세서간의 통신을 메세지패씽(message-passing)에 의존하는데 현재의 기술수준하에서는 이 통신속도가 실수계산속도에 비해 매우 느리므로 종래의 메모리공유컴퓨터에서와는 달리 데이터통신량을 최소화하는 알고리듬이 요구된다. 블록 SOR에 다중색채기법을 가미한 알고리듬이 그 한 예로써 우리는 이를 CM-5에서 구현한 결과 N=512x512 행렬에서 프로세서의 수가 16에서 512의 범위 하에서 50%의 효율을 실현하였다. 반면 종래의 효율적인 병렬 준비행렬로 알려진 ADI알고리듬은 방대한 량의 데이터통신 때문에 매우 열등한 결과를 보여준다. In this paper we present two preconditioners for solving large sparse linear systems arising from elliptic partial differential equations on massively parallel machines, such as the CM-5. Most massively parallel machines do heavily rely on the message-passing for the interprocessor communications, but according to the current manufacturing standards the cost of communications is very high compared to that of floating point arithmetic computations. Due to this we need an algorithm which minimizes the amount of interprocessor communication on the massively parallel machines. We will show that Block SOR(SuccessiveOverRelaxation) method coupled with the multi-coloring technique is one of such preconditioner on the massively parallel machines, by conducting experiments on the CM-5. Also, we implemented the ADI(AlternatingDirectionImplicit) method on the CM-5, which has been conventionally one of the most powerful parallel preconditioner. Our experiment shows that Block SOR method coupled with the multi-coloring technique could yield a speedup with 50% efficiency with the range of number of processors from 16 to 512 for a matrix with dimension 512x512. On the other hand, the ADI method shows a very poor performance.

알고리즘 : CRAY-2 에서의 대형희귀행렬 연립방정식의 해법을 위한 벡터준비행렬의 재배열방법

마상백(Ma Sang Back) 한국정보처리학회 1995 정보처리학회논문지 Vol.2 No.6

이 논문에서는 우리는 CRAY-2 에서 편미분방정식에서 발생하는 대형희귀연립방정식의 효과적인 벡터 준비행렬을 만들기 위한 재배열방법을 제시한다. 이 재배열방법은 종래의 빨강/검정 배열의 선형 형태로써, ILU 준비행렬의 변형 형태에 사용될 경우 필인(fill-in)을 크게 하면 종래의 빨강/검정 재배열의 약점이던 수렴율의 감소를 극복할 수 있다. 우리는 CRAY-2 에서 여러 가지 실험을 통해 우리의 주장을 입증한다. 또, 에러 행렬의 후로베니우스 놈을 계산한 결과도 우리의 주장과 일치한다. In this paper we present a reordering scheme that could lead to efficient vectorization of the preconditioners for the large sparse linear systems arising from partial differential equations on the CRAY-2. This reordering scheme is a line version of the conventional red/black ordering. This reordering scheme, coupled with a variant of ILU(Incomplete LU) preconditioning, can overcome the poor rate of convergence of the conventional red/black reordering, if relatively large number of fill-ins were used. We substantiate our claim by conducting various experiments on the CRAY-2 machine. Also, the computation of the Frobenius norm of the error matrices agree with our claim.

CRAY -2 에서 멀티 / 미이크로 태스킹 라이브러리를 이용한 선형시스템의 병렬해법

마상백(Ma Sang Back) 한국정보처리학회 1997 정보처리학회논문지 Vol.4 No.11

Multitasking and microtasking on the CRAY machine provides still another way to improve computational power. Since CRAY-2 has 4 processors we can achieve speedup up to 4 with properly designed algorithms. In this paper we present two parallelizations of linear system solution on the CRAY-2 with multitasking and microtasking library. One is the LU decomposition on the dense matrices and the other is the iterative solution of large sparse linear systems with the preconditioner proposed by Radicati di Brozolo. In the first case we realized a speedup of 1.3 with 2 processors for a matrix of dimension 600 with the multitasking and in the second case a speedup of around 3 with 4 processors for a matrix of dimension 8192 with the microtasking. In the first case the speedup is limited because of the nonuniform vector lengths. In the second case the ILU(0) preconditioner with Radicati's technique seem to realize a reasonably high speedup with 4 processors.

레이레이 계수의 최소화에 의한 내부고유치 계산을 위한 병렬준비행렬들의 비교

마상백,장호종,Ma, Sang-back,Jang, Ho-Jong 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.2

최근에 CG 반복법을 이용하여 레이레이 계수를 최소화함으로써 대칭행렬의 내부고유치를 구하는 방법이 개발되었다 그리고 이 방법은 병렬계산에 매우 적합하다. 적절한 준비행렬의 선택은 수렴속도를 향상시킨다. 우리는 본 연구에서 이를 위한 병렬준비행렬들을 비교한다. 고려된 준비행렬들은 Point-SSOR, 다중색채하의 ILU(0)와 Block SSOR이다. 우리는 128개의 노드를 가진 CRAY-T3E에서 구현하였다. 프로세서간의 통신은 MPI 리이브러리를 사용하였다. 최고 512$\times$512 행렬까지 시험하였는데 이 행렬들은 타원형 편미분방정식의 근사화에서 얻어졌다. 그 결과 다중색채 Block SSOR이 가장 성능이 우수한 것으로 판명되었다. Recently, CG (Conjugate Gradient) scheme for the optimization of the Rayleigh quotient has been proven a very attractive and promising technique for interior eigenvalues for the following eigenvalue problem, Ax=λx (1) The given matrix A is assummed to be large and sparse, and symmetric. Also, the method is very amenable to parallel computations. A proper choice of the preconditioner significantly improves the convergence of the CG scheme. We compare the parallel preconditioners for the computation of the interior eigenvalues of a symmetric matrix by CG-type method. The considered preconditioners are Point-SSOR, ILU (0) in the multi-coloring order, and Multi-Color Block SSOR (Symmetric Succesive OverRelaxation). We conducted our experiments on the CRAY­T3E with 128 nodes. The MPI (Message Passing Interface) library was adopted for the interprocessor communications. The test matrices are up to $512{\times}512$ in dimensions and were created from the discretizations of the elliptic PDE. All things considered the MC-BSSOR seems to be most robust preconditioner.