Algorithm level

Difference between revisions of "Repeated Thomas algorithm, pointwise version"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][checked revision]
 
(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'''
 

Latest revision as of 15:27, 14 March 2018


This page is currently available in Russian only. Push "Русский" on the left colomn to view the page.