|
|
| (50 intermediate revisions by 3 users not shown) |
| Line 1: |
Line 1: |
| | + | {{level-a}} |
| | | | |
| − | Primary authors of this description: A.V.Frolov, Vad.V.Voevodin (Section 2.2), A.M.Teplov (Section 2.4)
| + | {{Russian}} |
| | | | |
| − | '''Contents'''
| + | [[Category:Started articles]] |
| | | | |
| − | 1 Properties and structure of the algorithm
| + | [[ru:Классическая монотонная прогонка, повторный вариант]] |
| − | 1.1 General description of the algorithm
| |
| − | 1.2 Mathematical description of the algorithm
| |
| − | 1.3 Computational kernel of the algorithm
| |
| − | 1.4 Macro structure of the algorithm
| |
| − | 1.5 Implementation scheme of the serial algorithm
| |
| − | 1.6 Serial complexity of the algorithm
| |
| − | 1.7 Information graph
| |
| − | 1.8 Parallelization resource of the algorithm
| |
| − | 1.9 Input and output data of the algorithm
| |
| − | 1.10 Properties of the algorithm
| |
| − | 2 Software implementation of the algorithm
| |
| − | 2.1 Implementation peculiarities of the serial algorithm
| |
| − | 2.2 Locality of data and computations
| |
| − | 2.2.1 Locality of implementation
| |
| − | 2.2.1.1 Structure of memory access and a qualitative estimation of locality
| |
| − | 2.2.1.2 Quantitative estimation of locality
| |
| − | 2.3 Possible methods and considerations for parallel implementation of the algorithm
| |
| − | 2.4 Scalability of the algorithm and its implementations
| |
| − | 2.4.1 Scalability of the algorithm
| |
| − | 2.4.2 Scalability of of the algorithm implementation
| |
| − | 2.5 Dynamic characteristics and efficiency of the algorithm implementation
| |
| − | 2.6 Conclusions for different classes of computer architecture
| |
| − | 2.7 Existing implementations of the algorithm
| |
| − | 3 References
| |
| − | | |
| − | | |
| − | '''1 Properties and structure of the algorithm'''
| |
| − | | |
| − | '''1.1 General description of the algorithm'''
| |
| − | | |
| − | The '''two-sided elimination method''' is a variant of Gaussian elimination used for solving a system of linear algebraic equations (SLAE) [1][2] Ax = b, where
| |
| − | | |
| − | A = \begin{bmatrix}
| |
| − | a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\
| |
| − | a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\
| |
| − | 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\
| |
| − | \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\
| |
| − | 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\
| |
| − | 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\
| |
| − | \end{bmatrix}, x = \begin{bmatrix}
| |
| − | x_{1} \\
| |
| − | x_{2} \\
| |
| − | \vdots \\
| |
| − | x_{n} \\
| |
| − | \end{bmatrix}, b = \begin{bmatrix}
| |
| − | b_{1} \\
| |
| − | b_{2} \\
| |
| − | \vdots \\
| |
| − | b_{n} \\
| |
| − | \end{bmatrix}
| |
| − | | |
| − | However, presentations of the elimination method [3] often use a different notation and a numbering for the right-hand side and matrix of the system. For instance, the above SLAE can be written as
| |
| − | | |
| − | A = \begin{bmatrix}
| |
| − | c_{0} & -b_{0} & 0 & \cdots & \cdots & 0 \\
| |
| − | -a_{1} & c_{1} & -b_{1} & \cdots & \cdots & 0 \\
| |
| − | 0 & -a_{2} & c_{2} & \cdots & \cdots & 0 \\
| |
| − | \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\
| |
| − | 0 & \cdots & \cdots & -a_{N-1} & c_{N-1} & -b_{N-1} \\
| |
| − | 0 & \cdots & \cdots & 0 & -a_{N} & c_{N} \\
| |
| − | \end{bmatrix}\begin{bmatrix}
| |
| − | y_{0} \\
| |
| − | y_{1} \\
| |
| − | \vdots \\
| |
| − | y_{N} \\
| |
| − | \end{bmatrix} = \begin{bmatrix}
| |
| − | f_{0} \\
| |
| − | f_{1} \\
| |
| − | \vdots \\
| |
| − | f_{N} \\
| |
| − | \end{bmatrix}
| |
| − | | |
| − | (here, N=n-1). If each equation is written separately, then we have
| |
| − | | |
| − | c_{0} y_{0} - b_{0} y_{1} = f_{0},
| |
| − | -a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1,
| |
| − | -a_{N} y_{N-1} + c_{N} y_{N} = f_{N}.
| |
| − | | |
| − | Similarly to the classical (monotone) elimination method, the two-sided variant eliminates unknowns in a system; however, unlike the former, it simultaneously performs elimination from both corners (the upper and lower ones) of the SLAE. In principle, the two-sided elimination can be regarded as the simplest version of the reduction method (in which m = 1 and monotone eliminations are conducted in opposite directions).
| |
| − | | |
| − | | |
| − | '''1.2 Mathematical description of the algorithm'''
| |
