[关闭]
@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 , where is problem specified and is arbitrary. can be written in , where is the diagonal part and is below the diagonal.
The Gauss-Seidel iteration is to update an approximate solution by
Poisson's equation
In our problem is defined as the matrix corresponding to the approximation of the Laplacian operator . So, actually our mission is to solve Poisson's equation


Application

Here are some application of poisson's equation:


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 . Namely, the procedure is known to converge if either:

Fortunately, here we have is symmetric positive-definite.

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

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

The time complexity of each iteration is , where is the length of . However in our scenario, most of are s. The non-zero entries for a fixed is 27. So actually the time complexity is reduced to
Let's consider it's asymptotic performance:
For each iteration, . Denote as and as
So
We denote as the limitation of . We have where is the largest absolute eigen value of . If we want to control the error less than , then the time complexity of the algorithm is , where

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, . So totally, we need interations. Further more, in each iteration we need update components of . For updating each component, we need to do 54 calculations in total. So the number of arithmetic and logical operations is , where .

Characterize the space requirements

We only have to store the double vector , which is 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.
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注