flâneur

Forward substitution - Algowiki

algowiki-project.org · 1,796 words · saved by 1 readers

Forward substitution is the process of solving a system of linear algebraic equations (SLAE) 𝐿𝑥=𝑦 with a lower triangular coefficient matrix 𝐿 . The matrix 𝐿 is a factor of the matrix 𝐴 and results from either the 𝐿𝑈 -decomposition of the latter obtained by any of numerous ways (such as simple Gaussian elimination or Gaussian elimination with pivoting or compact schemes of Gaussian elimination) or other types of decomposition. The triangular form of 𝐿 ensures that the process of solving a SLAE is a modification of the general substitution method and this process can be described by simple formulas. In[1], the process of solving a SLAE with a lower triangular coefficient matrix was named the back substitution. It was also noted in [1] that, in the literature, back substitution is usually regarded as solving a SLAE with a right triangular matrix, whereas the solution of left triangular systems is called the forward substitution. We adopt this nomenclature in order to a

Forward substitution - Algowiki Forward substitution From Algowiki Jump to navigation Jump to search Forward substitution Sequential algorithm Serial complexity [math]\displaystyle{ O(n^2) }[/math] Input data [math]\displaystyle{ O(n^2) }[/math] Output data [math]\displaystyle{ n }[/math] Parallel algorithm Parallel form height [math]\displaystyle{ O(n) }[/math] Parallel form width [math]\displaystyle{ O(n) }[/math] Primary authors of this description: A.V.Frolov . Contents 1 Properties and structure of the algorithm 1.1 General description of the algorithm 1.2 Mathematical description of the

related reading