square65_blue.gif 4.1 Definition and Examples

     

    우리는 앞에서 여러 가지 문제에 대해서 그를 해결하는 하나의 방법인 Algorithm에 대하여 배웠다. 그러면 이를 기반으로 하여 이를 실제적으로 Numerical한 관점에서는 어떠한 Algorithm이 좋고 이를 실제로 Computer에 어떻게 적용하고, 더 효율적인 (Effective) 방법이 있는지, 그리고 이를 효율적으로 이미 활용하고 있는 Mathematical Software에는 어떤 것들이 있는지 알아보도록 하자.

    이를 위하여는 Computer 내부에서 임의의 연산을 하는데, 그것이 정확해야 한다. 그것은 이미 앞의 Stability에서 언급한 바 있다. 그러면 그러한 Stable algorithm의 문제해결을 하는데, 현재 주워저 있는 연산장비에 적용하기에 너무 느리다면 어떻게 될 것인가? 아마도 그러한 Algorithm은 경제성이 없다고 판단될 수 있다.

    따라서 우리는 실제로 Computer의 내부에서 얼마나 오랫동안 계산을 해야 하는지 파악해야 한다. 이것을 수월하게 이해하기 위해서 우리는 연산에 걸리는 시간을 임의대로 설정하여 그것을 하나의 단위로 정의하도록 하자.

    dia_bluve.gif Definition 4.1.1 [Flop]

    앞에서 우리가 언급한 Floating Point Number를 중심으로 이를 이용하여 하나의 단위의 연산(예를 들면 한번의 더하기, 한번의 곱하기, 한번의 빼기, 한번의 나누기)를 수행하는데 걸리는 시간의 총 합을 floating point operation이라 하고, 이를 줄여서 flop이라 한다. 또한 이러한 flop이 어떠한 algorithm을 수행하는데 얼마나 많이 나오는지 체크하는 것을 flop count라고 한다.

    이러한 flop의 개수는 일반적으로 big O notation이라 불리우는 함수에 의하여 총 시간이 계산되어 질 수 있다. 즉 다음과 같은 표현을 사용할 수 있다는 의미이다.

flop의 개수소요된 총 시간

    따라서 우리는 이를 바탕으로 임의의 algorithm이 수행되는데 걸린 시간을 체크할 수 있게 된다. 이를 통하여 일반적으로 현대의 컴퓨터들을 기준으로 두고 살펴볼 때 행렬에 관련된 임의의 algorithm이 시간내에 출 수 있을 정도로 effective하다는 이야기는 아래의 정의와 같이 할 수 있다.

    dia_bluve.gif Definition 4.1.2 [Effectiveness]

    차원을 가지는 행렬의 연산을 하는 과정에서 수행되는 총 시간이 보다 적게 걸리는 algorithm을 effective algorithm이라 부른다.

    따라서 algorithm을 구성하는 과정에서는 실제로 stable의 여부도 중요하지만, 이제는 effectiveness도 생각을 해야 한다는 것이다. 예를 들어 Cramer의 law을 이용하여 어떠한 Linear System의 해를 구하는 과정은 상당히 stable하고 정확한 값에 더욱 더 가까이 갈 수 있다. 그러나, 이 algorithm은 의 시간이 소요된다. 이러한 algorithm은 절대로 effective하다고 할 수 없기 때문에 실제로 해를 구하는 방법으로 쓰지 않는 것이다. (위의 을 구하는 방법은 Chapter 6장에 있습니다.)

    마지막으로 하나의 Notation을 소개하겠다.

    dia_brown.gif Notation

    본 내용에서 는 이제부터 의 값을 의 값에 덮어쓰겠다(overwrite)는 의미로 사용하겠다. 또한 의 값을 바꾸겠다라는 의미로 사용하도록 하겠다. 이러한 기호는 모두 computer science에서 시작된 기호들로서, 수학에서는 다른 의미로 해석될 수 있으나, 여기서는 이러한 표기를 따르도록 하겠다.

     

bar01_dot1x1_black.gif

square65_green.gif 3.2 Flop Count and Storage Considerations for Some Basic Algorithms

     

보통 차원 행렬에 대한 정보를 저장하기 위해서는 개 만큼의 저장공간이 필요하다. 이 저장공간은 Computer나 연산장치에 있어서도 유한하기 때문에 이를 줄이는 것도 Effective한 algorithm을 구성하는데 큰 도움이 된다.

예를 들어 triangular matrix의 정보를 저장하는 데에는 의 공간이면 충분히 확보할 수 있으며, sparse matrix라 불리우는 0의 정보가 상당히 많이 포함하는 matrix의 경우에도 원소중 0이 아닌 원소에 대해서만 저장을 하면 되므로, 상당히 많은 양의 저장공간을 줄일 수 있다.

따라서 Effectiveness를 따지는 경우에는 위에서 언급한 flop count뿐만이 아니라 저장공간에 대해서도 최적화할 수 있는 방안이 있는지 고려해 보는 것은 매우 중요한 문제이다.

Dominated Operation Count

일반적으로 flop의 개수를 산출하는 경우에는 그 개수가 원래의 문제에 주어진 input data의 크기에 의하여 많이 의존된다. 따라서 input data를 일반적으로 미지수 으로 둔다면 flop은 에 관한 함수의 형태로 나타난다.

문제는 이러한 함수의 형태에서 값이 커짐에 따라 비중이 높아지는 부분과 그렇지 않은 부분으로 나뉜다. 예를 들어 flop이 이 된다면 이 증가함에 따라 은 크게 증가하지만 은 그보다 작게 증가한다. 따라서 그 수가 엄청나게 커질 경우 은 연산의 회수로서의 의미가 굉장히 작아지게 된다.

따라서 일반적으로 input data의 크기가 많이 변하는 부분만을 flop으로 사용하는 것이 일반적이다. 위의 경우에도 flop은 이 아니라 이 flop이 된다.

bar05_solid1x1_blue.gif

dia_bluve.gif Example 4.2.1

차원 vector들의 Inner product를 생각해 보자. 이 경우 pseudo code를 보면

    For do

이므로 번의 flop이 필요하다.

    Inner Product의 경우에는 위와 같이 간단하고 상당히 effective한 algorithm이라 할 수 있다. 그러면 Outer Product의 경우는 어떠한가? 이 경우에는 그 결과값이 Matrix의 형태로 나타나게 된다. 따라서 그 저장공간도 개가 필요하며, flop도 개만큼 필요하게 된다.

    차 Matrix와 차원 vector의 곱도 마찬가지로 판단한다면 번의 곱과 각각의 원소에 대하여 회의 곱으로 구성되므로 회의 연산으로 이루어진다. 단, 회의 flop은 이 커짐에 따라 그 의미를 잃으므로 flop은 이 된다.

    이런식으로 여러 가지 행렬 연산상의 flop을 계산해 볼 수 있다. 이를 정리해보자.

Flop count for the product of two triangular matrices

차원인 경우 연산하는 경우의 수는 이 된다.

bar05_solid1x1_darkyellow.gif

Flop count for the product of two matrices

행렬이 이고, 행렬이 일 경우 flop은 가 된다. 특히 모두 차 정사각행렬일 경우 flop은 이 된다.

bar05_solid1x1_green.gif

Flop count for the product

행렬이 이고, vector가 차원 vector라면 그 flop은 이 된다. 자연스럽게, 이라면 그 flop은 이 될 것이다.

bar05_solid1x1_purple.gif

Flop count for the Back Substitution on upper triangular matrix

개의 미지수를 가진 Linear System이라면 그 System의 Back Substitution과정은 이다.

bar05_solid1x1_red.gif

Flop count for the computing inverse matrix for upper triangular matrix

그 flop은 이다.

 

bar01_dot1x1_blue.gif

square65_orange.gif 4.3 Some Existing High-Quality Mathematical Software for Linear Algebra Problems

     

    위와 같은 Effective한 Algorithm을 가지는Mathematical Software가 어떤 것들이 있는지 알아보자.

    4.3.1. LINPACK

http://www.netlib.org/linpack/

LINPACK is a collection of Fortran subroutines that analyze and solve linear equations and linear least-squares problems. The package solves linear systems whose matrices are general, banded, symmetric indefinite, symmetric positive definite, triangular, and tridiagonal square. In addition, the package computes the QR and singular value decompositions of rectangular matrices and applies them to least-squares problems. LINPACK uses column-oriented algorithms to increase efficiency by preserving locality of reference.

LINPACK was designed for supercomputers in use in the 1970s and early 1980s. LINPACK has been largely superceded by LAPACK, which has been designed to run efficiently on shared-memory, vector supercomputers.

    4.3.2. EISPACK

http://www.netlib.org/eispack/

EISPACK is a collection of Fortran subroutines that compute the eigenvalues and eigenvectors of nine classes of matrices: complex general, complex Hermitian, real general, real symmetric, real symmetric banded, real symmetric tridiagonal, special real tridiagonal, generalized real, and generalized real symmetric matices. In addition, two routines are included that use singular value decomposition to solve certain least-squares problems.

EISPACK has been superseded for the most part by LAPACK.

    4.3.3. LAPACK

http://www.netlib.org/lapack/

LAPACK is written in Fortran77 and provides routines for solving systems of simultaneous linear equations, least-squares solutions of linear systems of equations, eigenvalue problems, and singular value problems. The associated matrix factorizations (LU, Cholesky, QR, SVD, Schur, generalized Schur) are also provided, as are related computations such as reordering of the Schur factorizations and estimating condition numbers. Dense and banded matrices are handled, but not general sparse matrices. In all areas, similar functionality is provided for real and complex matrices, in both single and double precision.

If you're uncertain of the LAPACK routine name to address your application's needs, check out the LAPACK Search Engine.

The original goal of the LAPACK project was to make the widely used EISPACK and LINPACK libraries run efficiently on shared-memory vector and parallel processors. On these machines, LINPACK and EISPACK are inefficient because their memory access patterns disregard the multi-layered memory hierarchies of the machines, thereby spending too much time moving data instead of doing useful floating-point operations. LAPACK addresses this problem by reorganizing the algorithms to use block matrix operations, such as matrix multiplication, in the innermost loops. These block operations can be optimized for each architecture to account for the memory hierarchy, and so provide a transportable way to achieve high efficiency on diverse modern machines. We use the term "transportable" instead of "portable" because, for fastest possible performance, LAPACK requires that highly optimized block matrix operations be already implemented on each machine.

LAPACK routines are written so that as much as possible of the computation is performed by calls to the Basic Linear Algebra Subprograms (BLAS). While LINPACK and EISPACK are based on the vector operation kernels of the Level 1 BLAS, LAPACK was designed at the outset to exploit the Level 3 BLAS -- a set of specifications for Fortran subprograms that do various types of matrix multiplication and the solution of triangular systems with multiple right-hand sides. Because of the coarse granularity of the Level 3 BLAS operations, their use promotes high efficiency on many high-performance computers, particularly if specially coded implementations are provided by the manufacturer.

Highly efficient machine-specific implementations of the BLAS are available for many modern high-performance computers. For details of known vendor- or ISV-provided BLAS, consult the BLAS FAQ. Alternatively, the user can download ATLAS to automatically generate an optimized BLAS library for the architecture. A Fortran77 reference implementation of the BLAS in available from netlib; however, its use is discouraged as it will not perform as well as a specially tuned implementation.

    4.3.4. NETLIB

    위의 수학적 algorithm들을 Fortran과 C의 형태로 재구성된 Library를 제공하고, 계속 향상시켜나가는 모임. 모든 분야에 많은 형태로 퍼져 있어서, 대부분의 수학적 algorithm이 집결되어 있는 곳이기도 하다.

http://www.netlib.org/

    4.3.5. NAG (Numerical Algorithm Group)

    다양한 Numerical Algorithm을 제공하는 Group. 수치해석적 분야가 강하다.

http://www.nag.co.uk/

    4.3.6. IMSL (International Mathematical and Statistical Library)

    Visual Numerics Inc.에서 제공하는 수학적 Algorithm. 상용으로서 그 안전성 및 신뢰도가 검증되어 있는 Library를 제공한다. 특히 수치해석적인 분야와 통계학적인 분야에 많은 Library를 제공한다.

http://www.vni.com/products/imsl/

    4.3.7. MATLAB

    Mathwork Inc.가 개발한 수학문제해결을 위한 종합적 Software. 거의 모든 수학분야에 이용된다.

http://www.mathworks.com/

    4.3.8. MATLAB code and MATCOM

    MATLAB의 삽입되어 들어갈 수 있는 Module을 구성할 수 있는 MATLAB Code를 개발하는 곳이다. 대부분이 C로 이루어져 있다.

http://www.mathtools.net/

    4.3.9. The ACM(Association for Computing Machinery)Library

    미국의 NIST에서 지원하고 있는 ACM에서 제작한 Journal로 최신의 수학적 Algorithm을 소개하는 Journal이다.

http://www.acm.org/toms/

    4.3.10. ITPACK

http://www.ma.utexas.edu/CNA/ITPACK/

ITPACK, developed at the Center for Numerical Analysis, the University of Texas at Austin, is a collection of subroutines for solving large sparse linear systems by adaptive accelerated iterative algorithms.

 

bar01_dot1x1_blue.gif

Copyright © 2002, Made by SML(Sungkyunkwan Univ. Linear algebra Lab.), All rights reserved.