CSE6230 Final Project Checkpoint#1

---

Project: Gauss-Seidel iteration
Team Member: Haoming Jiang, Wenjie Yao

---

Problem fomulation

Gauss-Seidel Method:
We want to solve the linear system $Kv = b$, where $K$ is problem specified and $b$ is arbitrary. $K$ can be written in $K=L+D+L^T$, where $D$ is the diagonal part and $L$ is below the diagonal.
The Gauss-Seidel iteration is to update an approximate solution $v^i$ by $v^{i+1} \leftarrow v^i + (L+D)^{-1}(b-Kv^i)$
Poisson's equation
In our problem $K$ is defined as the matrix corresponding to the approximation of the Laplacian operator $\triangle$. So, actually our mission is to solve Poisson's equation $-\triangle u = b$

---

Application

Here are some application of poisson's equation:

• Poisson image editing [3]
• Electrostatics
• Newtonian gravity
• Hydrodynamics
• Diffusion

---

Asymptotic serial analysis

Asymptotic performance ("Big-O") of existing serial algorithms

Gerenally speaking, the convergence properties of Gauss–Seidel method are dependent on the Matrix $K$. Namely, the procedure is known to converge if either:

• $K$ is symmetric positive-definite
• $K$ is strictly or irreducibly diagonally dominant.

Fortunately, here we have $K$ is symmetric positive-definite.

According to [2]Thm 10.1.2, in our problem Gauss-Seidel iteration converges for any $v^0$.

The best way I found for doing Gauss-Seidel iteration is by using the following update formulation:

$$v^{k+1}_i = \frac{1}{k_{ii}}(b_i - \sum_{j=1}^{i-1}k_{ij}v^{k+1}_j - \sum_{j=i+1}^{n}k_{ij}v^{k}_j), i= 1,...,n$$

The time complexity of each iteration is $O(n^2)$, where $n$ is the length of $v$. However in our scenario, most of $k_{ij}$ are $0$s. The non-zero entries for a fixed $i$ is 27. So actually the time complexity is reduced to $O(n)$
Let's consider it's asymptotic performance:
For each iteration, $v^{i+1} \leftarrow v^i + (L+D)^{-1}(b-Kv^i) = (L+D)^{-1}b-(L+D)^{-1}L^Tv^i$. Denote $(L+D)^{-1}b$ as $b^*$ and $-(L+D)^{-1}L^T$ as $A$
So $v^{i+1} = (1+A+...+A^i)b^* + A^{i+1}v^0$
We denote $v^*$ as the limitation of $v^i$. We have $v^{i} - v^* = O(\lambda_{max}^i)$ where $\lambda_{max}^i$ is the largest absolute eigen value of $A$. If we want to control the error less than $\delta$, then the time complexity of the algorithm is $O(n\frac{log(\delta)}{log(\lambda_{max})})$, where $n=(N-1)^3$

The theoretical best lower bound on asymptotic performance

I can not find a better lowerbound on asymptotic performance.

The asymptotic performance of our code

It is the same as the above discussion.

Characterize the number of arithmetic and logical operations

In order to control the error, $||v^{i} - v^*||_2 \leq \frac{\lambda_{max}^{i}}{1-\lambda_{max}}||b^*||_2 \leq \delta$. So totally, we need $i = \frac{log ((1-\lambda_{max}) \delta/ ||b^*||_2)}{log(\lambda_{max})}$ interations. Further more, in each iteration we need update $n$ components of $v$. For updating each component, we need to do 54 calculations in total. So the number of arithmetic and logical operations is $54n\frac{log ((1-\lambda_{max}) \delta/ ||b^*||_2)}{log(\lambda_{max})}$, where $n=(N-1)^3$.

Characterize the space requirements

We only have to store the double vector $v$, which is $8n = 8(N-1)^3$ bytes.

---

Reference

1. Wikipedia Gauss-Seidel-method
2. Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
3. Pérez, Patrick, Michel Gangnet, and Andrew Blake. "Poisson image editing." ACM Transactions on graphics (TOG). Vol. 22. No. 3. ACM, 2003.