우리는 앞에서 여러
가지 문제에 대해서 그를 해결하는 하나의 방법인 Algorithm에
대하여 배웠다. 그러면 이를 기반으로 하여 이를 실제적으로
Numerical한 관점에서는 어떠한 Algorithm이 좋고 이를
실제로 Computer에 어떻게 적용하고, 더 효율적인 (Effective)
방법이 있는지, 그리고 이를 효율적으로 이미 활용하고
있는 Mathematical Software에는 어떤 것들이 있는지
알아보도록 하자.
이를 위하여는 Computer 내부에서
임의의 연산을 하는데, 그것이 정확해야 한다. 그것은
이미 앞의 Stability에서 언급한 바 있다. 그러면 그러한
Stable algorithm의 문제해결을 하는데, 현재 주워저
있는 연산장비에 적용하기에 너무 느리다면 어떻게
될 것인가? 아마도 그러한 Algorithm은 경제성이 없다고
판단될 수 있다.
따라서 우리는 실제로
Computer의 내부에서 얼마나 오랫동안 계산을 해야
하는지 파악해야 한다. 이것을 수월하게 이해하기 위해서
우리는 연산에 걸리는 시간을 임의대로 설정하여 그것을
하나의 단위로 정의하도록 하자.
Definition 4.1.1 [Flop]
앞에서 우리가 언급한 Floating Point Number를
중심으로 이를 이용하여 하나의 단위의
연산(예를 들면 한번의 더하기, 한번의
곱하기, 한번의 빼기, 한번의 나누기)를
수행하는데 걸리는 시간의 총 합을 floating
point operation이라 하고, 이를 줄여서
flop이라 한다. 또한 이러한 flop이
어떠한 algorithm을 수행하는데 얼마나
많이 나오는지 체크하는 것을 flop
count라고 한다.
이러한 flop의
개수는 일반적으로 big O notation이라 불리우는 함수에
의하여 총 시간이 계산되어 질 수 있다. 즉 다음과
같은 표현을 사용할 수 있다는 의미이다.
flop의 개수소요된 총 시간
따라서 우리는 이를
바탕으로 임의의 algorithm이 수행되는데 걸린 시간을
체크할 수 있게 된다. 이를 통하여 일반적으로 현대의
컴퓨터들을 기준으로 두고 살펴볼 때 행렬에 관련된
임의의 algorithm이 시간내에 출 수 있을 정도로 effective하다는
이야기는 아래의 정의와 같이 할 수 있다.
Definition 4.1.2 [Effectiveness]
차원을 가지는 행렬의 연산을 하는 과정에서 수행되는 총 시간이 보다 적게 걸리는 algorithm을 effective algorithm이라 부른다.
따라서 algorithm을
구성하는 과정에서는 실제로 stable의 여부도 중요하지만,
이제는 effectiveness도 생각을 해야 한다는 것이다.
예를 들어 Cramer의 law을 이용하여 어떠한 Linear
System의 해를 구하는 과정은 상당히 stable하고 정확한
값에 더욱 더 가까이 갈 수 있다. 그러나, 이 algorithm은
의 시간이 소요된다. 이러한 algorithm은 절대로 effective하다고 할 수 없기
때문에 실제로 해를 구하는 방법으로 쓰지 않는 것이다.
(위의 을 구하는 방법은 Chapter 6장에 있습니다.)
마지막으로 하나의
Notation을 소개하겠다.
Notation
본 내용에서 는 이제부터 의 값을 의 값에 덮어쓰겠다(overwrite)는 의미로 사용하겠다. 또한 는 와 의 값을 바꾸겠다라는 의미로 사용하도록 하겠다. 이러한 기호는 모두 computer
science에서 시작된 기호들로서, 수학에서는
다른 의미로 해석될 수 있으나, 여기서는
이러한 표기를 따르도록 하겠다.
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이 된다.
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
차원인 경우 연산하는 경우의 수는 이 된다.
Flop
count for the product of two matrices
행렬이 이고, 행렬이 일 경우 flop은 가 된다. 특히 모두 차 정사각행렬일 경우 flop은 이 된다.
Flop
count for the product
행렬이 이고, vector가 차원 vector라면 그 flop은 이 된다. 자연스럽게, 이라면 그 flop은 이 될 것이다.
Flop
count for the Back Substitution on
upper triangular matrix
개의 미지수를 가진 Linear System이라면 그 System의 Back Substitution과정은
이다.
Flop
count for the computing inverse matrix
for upper triangular matrix
그 flop은
이다.
4.3 Some
Existing High-Quality Mathematical Software for Linear
Algebra Problems
위와 같은 Effective한
Algorithm을 가지는Mathematical Software가 어떤 것들이
있는지 알아보자.
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.
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.
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이 집결되어
있는 곳이기도 하다.