@HaomingJiang 2017-09-29T02:46:09.000000Z 字数 2919 阅读 956

# 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:

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.

• 私有
• 公开
• 删除