# Solving a linear system whose matrix has imbalanced diagonal entries

I am trying to solve following set of equations:

A(i,i-2)*u(i-2) + A(i,i-1)*u(i-1) + (A(i,i)+β(i) )*u(i) + A(i,i+1)*u(i+1) + A(i,i+2)*u(i+2)= B(i) + β(i)

where i=1:1000000

If values of β varies(several orders) greatly then what would be the best strategy to solve this equation numerically. Should I expect oscillations in the result?

What could be the possible remedy?

*Is it okay if I add "10000*u(i)" on both sides of equations while solving iteratively?*

EDIT: Structure of Coeffcient Matrix will roughly look like this (if i=1:9, while I am trying to do it for i=1:10^6): $$\begin{bmatrix} A11 + β1& A12& A13& 0& 0& 0& 0& 0& 0& \\ A21& A22 + β2& A23& A24& 0& 0& 0& 0& 0& \\ A31& A32& A33 + β3& A34& A35& 0& 0& 0& 0& \\ 0& A42& A43& A44 + β4& A45& A46& 0& 0& 0& \\ 0& 0& A53& A54& A55 + β5& A56& A57& 0& 0& \\ 0& 0& 0& A64& A65& A66 + β6& A67& A68& 0&\\ 0& 0& 0& 0& A75& A76& A77 + β7& A78& A79& \\ 0& 0& 0& 0& 0& A86& A87& A88 + β8& A89& \\ 0& 0& 0& 0& 0& 0& A97& A98& A99 + β9& \\ \end{bmatrix}$$ Here A(i,i)=A(i,i-2)+A(i,i-1)+A(i,i+1)+A(i,i+2)

  **β(i,i)>0
β(i,i) >> A(i,i-2)+A(i,i-1)+A(i,i+1)+A(i,i+2)**


Also there is a huge variation in values of β.

**Order of every entry in matrix is ~10^-2, except diagonal entries and β which vary from order of 1 to 10^6.

• Can you show the matrix to make it easier to read the problem? It looks like you have ones on the two off diagonals in both directions, and then $1+\beta_i$ on the diagonal. Is this correct? Are the $\beta_i$ positive? – Wolfgang Bangerth Apr 22 '16 at 12:01
• @WolfgangBangerth: I have edited my question to show you the structure of matrix. Yes! it is like having ones on the two off diagonals in both directions, and then 1+β(i) on the diagonal. β(i) is always positive. – Hanumat Apr 22 '16 at 13:10
• If you're stuck with an iterative method, @namRakes is correct about scaling (preconditioning) the equation by the diagonal. Diagonal preconditioning should be very effective since your matrix seems to be diagonally dominant. – Charles Apr 25 '16 at 7:11

## 1 Answer

Answer depends on my assumptions about your question:

1. Is there a typo in your expression for the $i^{\text{th}}$ equation's diagonal term, which you say is $A_{i,i} + \beta_i$ at the top of the page. Then if I try using this with your expression for $A_{i,i}$ below the matrix, then I get $1+2\beta_i$ in the diagonal. Assuming that this is indeed a typo, then ...

2. Is $\beta_i >> B_i$ also? If so, given that $\beta_i >> \sum_{k=i-2,k\ne i}^{i+2} A_{i,k}$, your solution vector $u_i$ is centered around $\{1,1,1,...\}$. This is good news, because then this could be your initial guess for any iterative scheme.

You can also use direct solver with 1M equations, and should be able to get a reasonable performance with recent laptops and desktops.

• Thanks for Answer. Yes! that was typo error. But what about the large variation in values of β(i)? Will it create problem while solving iteratively? – Hanumat Apr 22 '16 at 17:11
• As long as $\beta_i >> B_i$ and $>> \sum A_{i,k}$ as above, and even with 10 orders of variation of $\beta_i$ your iterative scheme should work. If it doesn't converge, or the $\beta$ variation is 20 orders, you can try to scale each equation $i$ by $\beta_i$. Is there any reason you don't want to choose a direct solution method? – NameRakes Apr 22 '16 at 17:35