- Types of linear solvers
- What are the two main methods of solving linear systems?
- If you have a system with 10,000 equation, would you use a direct method?
- Gauss elimination
- Algorithm
- What are the two parts and how do they work?
- Cost
- How does the computational cost scale with the number of unknowns $n$?
- If you double the number of equations in a linear system, by what factor does the computational cost change for the two portions of the algorithm?
- Can you explain why in terms of what is happening with the algorithm?
- Pivoting
- Why is it used?
- There are two main types, which do we use?
- How is it done conceptually? How is it actually implemented?
- Scaling
- Why is it important to use scaling when doing pivoting?
- LU Decomposition
- How is it related to Gauss Elimination?
- When is LU decomposition more obviously preferred to Gauss Elimination?
- Thomas algorithm
- Why don’t we use pivoting and scaling with the Thomas algorithm?
- If you double the number of equations in a tridiagonal linear system, by what factor does the computational cost change?
Fill in the following psuedo code
- Assume array indexes start at zero.
- Assume loops start and end on the values listed (unlike
range).
- This is something to reason through, not something to memorize!
loop over columns: do k= __, __
loop over rows: do i= __, __
find fac: fac= a(__,__)/a(__,__)
loop row elements: do j= ,
a(__,__)=a(__,__) - fac*a(__,__)
end
do b vector b(__) = b(__) - fac*b(__)
end
end