# Finite differences on domains with irregular boundaries

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)?

-
For which purpose? Introduction for students at the very beginning? And what is a irregular geometry in your case? Domains with reentrant corners? – shuhalo Jan 12 '12 at 17:11
@Martin: I am biginner in this field. I need it for solving poisson equation using itterative methods on irregularly shaped domains, especially thoes with curved bundaries (eg.2-D circular domain) – liona Jan 12 '12 at 18:21
@last Please edit the question title and body to make it clear what you are asking. Specify the kinds of equations that you care about. Are you interested in discretizations, algebraic solvers, or both? Do you care about finite difference vs. finite elements (scicomp.stackexchange.com/questions/290/…)? Your current question is extremely broad and it's difficult to find in search. – Jed Brown Jan 12 '12 at 19:33
@JedBrown: I want to solve poisson equation using finite difference on given domain and boundary condition. – liona Jan 12 '12 at 20:26
last, please edit the body of your question to include the information in both of your comments to date. Also, as JedBrown said, please also edit the title of your question so that it's easier for people to search for your question, and easier for people to judge if the question might be interesting or applicable to them. – Geoff Oxberry Jan 12 '12 at 21:27

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.

-
Is there a way that I can improve the format of the matrix values that I posted... it doesn't look quite the way I'd like for it to look – Paul Jan 13 '12 at 15:52
Yes, you could use MathJax and put them in an array environment. – David Ketcheson Jan 13 '12 at 19:29
You're right... it looks a lot nicer with MathJax. Thanks for the suggestion :) – Paul Jan 13 '12 at 22:13
@Paul: Thank you for your simple solution! However How I can compute boundary points to obtain inside points for enclosed region between rectangular and triangle or (enclosed region between rectangular and circle)? – liona Jan 14 '12 at 7:02
Do you have a picture of the shape of the domain that you want to model? It's always easier to see it, than to describe it just in words :) – Paul Jan 14 '12 at 14:11

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

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.

-

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

-

I think that making the mesh fit the boundary and hence a departure from the standard square mesh of the fdm is probably a solution but nevertheless has serious implications as to the use of high order algorithms - difficult if not impossible. I have taken a different approach, namely keep the rectangular grid over the curved boundary geometry, create high order algorithms, interpolate from the boundary to set the values "outside" the geometry, and that's all there is. we have achieved precisions in concentric sphere test geometries of ~1e-12 with this method using an order 8 algorithm. if you will google "Edwards, fdm curved boundary" you will find references to my work.

-

Would it be possible for you to use adaptive mesh refinement? A quick Google search will turn up lots of links. AMR is used, for example, in fluid dynamics to model flow past complicated shapes; as well as many other applications. Here is an example of solving systems of hyperbolic conservation laws that arise in star formation. The geometries are very complex. The first part of the paper is a nice tutorial. http://www.mpa-garching.mpg.de/lectures/ADSEM/SS05_Homann.pdf

-