## Forward Substitution:

Consider a set of equations in a matrix form $Ax=b$, where A is a lower triangular matrix with non-zero diagonal elements. The equation is re-written in full matrix form as

It can be solved using the following algorithm

From the DSP implementation point of view, computation of $x_1$ requires one FLoating Point Operation per Second (FLOPS) – only one division. Computing $x_2$ will require 3 FLOPS – 1 multiplication, 1 division and 1 subtraction, $x_3$ will require 5 FLOPS – 2 multiplications, 1 division and two subtractions. Thus the computation of $x_{mm}$ will require $(2n-1)$ FLOPS.

Thus the overall FLOPS required for forward substitution is $1+3+5+\cdots+(2m-1)$ $= m^2$ FLOPS

## Backward substitution:

Consider a set of equations in a matrix form $Ax=b$, where A is a upper triangular matrix with non-zero diagonal elements. The equation is re-written in full matrix form as

Solved using the following algorithm

This one also requires $m^2$ FLOPS.

## Recommended Books on Estimation Theory:

Mathuranathan

– Founder and Author @ gaussianwaves.com which has garnered worldwide readership. He is a masters in communication engineering and has 7 years of technical expertise in channel modeling and has worked in various technologies ranging from read channel design for hard drives, GSM/EDGE/GPRS, OFDM, MIMO, 3GPP PHY layer and DSL.
He also specializes in tutoring on various subjects like signal processing, random process, digital communication etc..,He can be contacted at support@gaussianwaves.com