Finite differences on domains with irregular boundaries

Question

Can anybody help me to find the books on numerical solutions(finite difference and Crank–Nicolson methods) of Poisson and diffusion equations including examples on irregular geometry, such as a domain consisting of the area between a rectangle and a circle (especially books or links on MATLAB code examples in this case)?

Answer 1

I think a good book at the very beginning is the book by Hackbusch:

http://books.google.com/books/about/Elliptic_differential_equations.html?id=-ZPc_JYJFHgC&redir_esc=y

In particular ch. 4.8, "Discretization in an Arbitrary Domain" might be interesting for you. The German version of that book can be downloaded for free (legally). I don't know whether this holds for the English version as well.

Answer 2

The key to making a finite difference scheme work on an irregular geometry is to have a 'shape' matrix with values that denote points outside, inside, and on the boundary of the domain. Say we had a shape like this:

$$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 2 & 2 & 2 & 2 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 2 & 2 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{matrix} $$

The true domain (where all the non-zero entries of the matrix are) form a triangle pointed downward. The 1's represent points on the boundary, while 2's represent interior points (unkowns, usually) We can assign node numbers as follows:

$$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0\\ 0 & 0 & -1 & 1 & 2 & 3 & 4 & 5 & 6 & -1 & 0 & 0\\ 0 & 0 & 0 & -1 & 7 & 8 & 9 & 10 & -1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & -1 & 11 & 12 & -1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{matrix} $$

Here, -1's represent the boundary locations. Then, you can run a finite difference scheme over all entries in the matrix, but use an if statement to execute your scheme only on the interior nodes (from 1 to 12). This approach is not the most efficient way to do it, but it will get the job done... if you can afford the memory, it might be good to store the (i,j) entries of all the interior nodes, and run a for loop only on those nodes.

To create the geometry directly, you can do one of two things:
1. Create a black & white image manually, and import it to your program (easiest to implement, but impossible to refine your spatial resolution dx or dy).
2. Write code that will create discrete representations of the basic shapes that you want for any spatial resolution that you choose (harder to implement, but more robust for general finite difference schemes of any spatial resolution dx or dy).

If you want to learn more about how to do this, you may want to consider watching these videos:
NPTEL Computer Graphics Course, Video 2 (Raster Graphics)
NPTEL Computer Graphics Course, Video 3 (Raster Graphics, continued)
Check them out, and let me know if this addresses your question.

Answer 3

I would suggest the following papers:

The finite difference method at arbitrary irregular grids and its application in applied mechanics - Liszka Orkisz

http://www.sciencedirect.com/science/article/pii/0045794980901492

Finite difference techniques for variable grids - Jensen

http://www.mendeley.com/research/finite-difference-techniques-variable-grids-7/

Solving parabolic and hyperbolic equations by the generalized finite difference method - Benito Urena Gavete

http://www.sciencedirect.com/science/article/pii/S037704270600687X

Basically they describe how to generate finite difference stencial for nonstructured/irregular meshes. I don't know any book that treat this specific topic in depth, but Randall LeVeque's book might have something about it. Here is the link for the author's webpage, which contain some Matlab m-files for finite differences.

http://faculty.washington.edu/rjl/booksnotes.html