http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
O(N log N) ALGORITHM FOR FINDING PRIMARY TANDEM REPEATS IN A DNA GENOMIC SEQUENCE
SANGBACK MA,HYEONG-HWA JUN 한국산업응용수학회 2005 Journal of the Korean Society for Industrial and A Vol.9 No.1
The genomes of organism are being published in an enormous speed. The genomes has a lot of intronic regions, and repeats constitute a substantial part of that. Repeats play a crucial role in DNA ?nger-printing, and detecting certain genomic diseases, such as Huntington disease, which has a high number of CAG repeats. Also, they throw important clues about the evolutionary history. Repeats are in two types, Tandem Repeats and Interspersed Repeats. In this paper we address ourselves to the problem of detecting Primary Tandem Repeats, which are tandem repeats that are not contained in any tandem repeats. We show that our algorithm takes O(n log n) time, where n is the length of genome.
CM - 5 에서 비정규적 구조를 가진 희소 다원 일차 연립방정식의 해법을 위한 ILU(0) 와 Block SOR / SSOR 조정행렬의 병렬화
마상백(Sangback Ma) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.5
일반적인 크기 N의 희소 다원일차 연립 방정식의 해를 구할때 다중채색방법은 O(N) 의 병렬성을 제공한다. 그러나 이방법은 조정된 CG 방법에서처럼 수렴율이 감소하는 단점을 가지고있다. 이러한 단점을 극복할수 있는 다른 방법은 파동전면방법으로서, 주어진 행렬에서 얻을 수 있는 병렬성을 추구한다. 이 경우 수렴율은 변하지 않으나 파동전면의 길이가 일정치 않기때문에 병렬성이 제한된다. 이 논문에서는 우리는 위의 두가지 방법을 CM-5에서 ILU(0)와 Block SOR/SSOR 조정행렬에 적용하여 그 결과를 비교 분석 하였다. 여러가지 문제에서 검사 해본 후 다중채색하의 ILU(0) 방법이 가장 우수한 것으로 입증되었다. When solving general sparse linear systems multi-coloring techniques can yield a parallelism of order N, where N is the dimension of the matrix. However, this approach suffers from the deterioration of the rate of convergence, as in preconditioned CG method. Another technique that does not suffer from this is the wavefront technique, which exploits parallelism available in the original matrix. The rate of convergence remains the same, but the maximum parallelism is limited by the lengths of the wavefronts, which are often nonuniform. In this paper we compare these two approaches on ILU(0) and Block SOR/SSOR preconditioners on the CM-5. We have found that for the problems tested ILU(0) with multicoloring technique outperforms the other alternatives.
Ma, Sangback 한국산업정보응용수학회 1999 한국산업정보응용수학회 Vol.3 No.2
The Helmholtz equation is very important in physics and engineering. However, solution of the Helmholtz equation is in general known as a very difficult phenomenon. For if the w is negative, the FDM discretized linear system becomes indefinite, whose solution by iterative method requires a very clever preconditioner. In this paper we assume that w is nonnegative, and determine the optimal p parameter for the three dimensional AD1 iteration for the Helmholtz equation. The ADI(Alternating Direction Implicit) method is also getting new attentions due to the fact that ~t is very suitable to the vector/parallel computers, for example, as a preconditioner to the Krylov subspace methods. However, classical ADI was developed for two dimensions, and for three dimensions it is known that its convergence behaviour is, quite different from that in two dimensions. So far, in three dimensions the so-called Douglas-Rachfbrd form of AD1 was developed. It is known to converge for a relatively wide range of p values but its convergence is very slow. In this paper we determine the necessary conditions of the p parameter for the convergence and optimal p for the three dimensional AD1 iteration of the Peaceman-khford form for the real Helrnholtz equation with nonnegative w. Also, we conducted some experiments which is in close agreement with our theory. 'This straightforward extension of Peaceman-rachford AD1 into three dimensions will be useful as an iterative solver itself or as a preconditioner to the the Krylov subspace methods, such as CG(Conjugate Gradient) method or GMRES(m).
A Parallel preconditioner for Generalized Eigenvalue Problems by CG-TYPE Method
MA, SANGBACK,JANG, HO-JONG 한국산업정보응용수학회 2001 한국산업정보응용수학회 Vol.5 No.2
In this study, we shall be concerned with computing in parallel a few of the smallest eigenvalues and their corresponding eigenvectors of the eigenvalue problem, Ax = λBx, where A is symmetric, and B is symmetric positive definite. Both A and B are large and sparse. Recently iterative algorithms based on the optimization of the Rayleigh quotient have been developed, and CG scheme for the optimization of the Rayleigh quotient has been proven a very attractive and promising technique for large sparse eigenproblems for small extreme eigenvalues. As in the case of a system of linear equations, successful application of the CG scheme to eigenproblems depends also upon the preconditioning techniques. A proper choice of the preconditioner significantly improves the convergence of the CG scheme. The idea underlying the present work is a parallel computation of the Multi-Color Block SSOR preconditioning for the CG optimization of the Rayleigh quotient together with deflation techniques. Multi-Coloring is a simple technique to obatin the parallelism of order n, where n is the dimension of the matrix. 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 problems were drawn from the discretizations of partial differential equations by finite difference methods.