The Sparse Matrix

New Site

2004-11-01T14:16:00.000-06:00

Because Blogger is slow, unwieldy, painful to use, and because it's about time I started really hacking a site for myself, I've moved The Sparse Matrix blog to a new home.

http://www.thesparsematrix.com

All my existing posts will remain here until I get the time (and strength) to wade through the slow Blogger interface and transfer them.

In all fairness, for a free blog-site, Blogger is actually one of the best. I imagine after some time dealing with the pain of bandwidth limits, roll-your-own software, etc., I'll be waxing nostalgic about my Blogger days, but right now, the pain which is Blogger is still too near. Here's hoping the new site doesn't crash and burn.

Jammie Nation

2004-09-12T22:45:00.000-05:00

I'm with Amy and N.Z. Bear. Jammies now! I want a pair, yo.

"Bloggers have no checks and balances . . . [it's] a guy sitting in his living room in his pajamas." -- Jonathan Klein

This is, of course, far too delicious a statement to simply ignore. Already, bloggers have taken it up as a badge of honor.

Welcome to Jammie Nation, where Dan Ra^ther gets his ass kicked by guys in pajamas.

Via Instapundit, "NO DISPUTING IT -- Blogs Are Major Players." Viva la revolucion. Left, Right, Center. Who cares? We don't need you anymore, Mr. Ra^ther. We can do for ourselves just fine now, thank you.

UPDATE: Welcome, Instapundit readers. Here's some funnage for you.

Worst. Photoshop. Ever.

UPDATE: BTW, I gotta give credit where credit is due for the "ass kicked by guys in pajamas" joke. Check point three in the post.

UPDATE: From the fertile digital-brownshirt pen of Sharon Gilbert via Weapon of Mass Distraction:

Oh, the comedy. The tearful, cotton-and-lycra hilarity of it all.

Global Check of Candidate Points

2002-03-22T13:12:00.000-06:00

Algorithm

Pseudocode

If the search is over points created with the Centroid method:

Loop over each candidate point ( P_cand ):
Loop over nodes of containing element for P_cand ( N_cand ):
Loop over surrounding elements of N_cand ( E_n-cand ):
If P_cand is a sufficient distance from the candidate point contained in E_n-cand, it can be accepted.

Else, it cannot be accepted.

Else If the search is over points created with the Advancing Front method:

Loop over each candidate point ( P_cand ):
Loop over the candidate points of containing element for P_cand ( P_{other_cand} ):
If P_cand is a sufficient distance from the P_{other_cand}, it can be accepted.

Else P_cand it cannot be accepted.
Loop over nodes of containing element for P_cand ( N_cand ):
Loop over surrounding elements of N_cand ( E_n-cand ):
If P_cand is a sufficient distance from the candidate points contained in E_n-cand, it can be accepted.

Else P_cand it cannot be accepted.

Area Coordinate Search

2002-03-22T13:07:00.000-06:00

Algorithm

Recursive

Name:	*Search*
Variables Received:	Element_search (first received is the element from which the ideal point was generated)
Variables Returned:	Whether or not the ideal point can be found ( Return 1: cannot or Return 0: can )
	Containing element for the ideal point ( Element_found )
	Weights for the distribution function values of the containing element's nodes ( PHI₁, PHI₂, and PHI₃ )

Pseudocode

Compute the area of Element_search ( Area_search ).

Compute the area of triangle made by the ideal point and Node 2 and Node 3 of Element_search:

Area₁ = (Point_n2-Point_ideal) x (Point_n3-Point_ideal)

Compute the area of triangle made by the ideal point and Node 3 and Node 1 of Element_search:

Area₂ = (Point_n3-Point_ideal) x (Point_n1-Point_ideal)

Compute the area of triangle made by the ideal point and Node 1 and Node 2 of Element_search:

Area₃ = (Point_n1-Point_ideal) x (Point_n2-Point_ideal)

Compute the minimum of these areas:

Area_min = MIN( Area₁, Area₂, Area₃ )

If Area_min is greater than the negative of the minimum distribution function (-PHI_min):

PHI₁ = Area₁/Area_search
PHI₂ = Area₂/Area_search
PHI₃ = Area₃/Area_search
Return 0

If Area₁ is negative:

Set Element_search to the neighboring element across from Point₁.

If this neighbor is not a boundary and hasn't already been searched:
Search the neighbor.

If the containing element is found (i.e. Search Returns 0 ):
Element_found = Element_search
Return 0
Else:
Return 1

Else:
Return 1

If Area₂ is negative:

Set Element_search to the neighboring element across from Point₂.

If this neighbor is not a boundary and hasn't already been searched:
Search the neighbor.

If the containing element is found (i.e. Search Returns 0 ):
Element_found = Element_search
Return 0
Else:
Return 1

Else:
Return 1

If Area₃ is negative:

Set Element_search to the neighboring element across from Point₃.

If this neighbor is not a boundary and hasn't already been searched:
Search the neighbor.

If the containing element is found (i.e. Search Returns 0 ):
Element_found = Element_search
Return 0
Else:
Return 1

Else:
Return 1

Centroid Method for Point Placement

2002-03-22T11:55:00.000-06:00

Algorithm

Pseudocode

Loop over each element in a given triangulation:

If the element is modifiable:
Compute the element's centroid:
centroid_x = (1/3)*(x₁ + x₂ + x₃)
centroid_y = (1/3)*(y₁ + y₂ + y₃)
Compute the centroid's distribution function value:
centroid_df = (1/3)*(df₁ + df₂ + df₃)
Compute the distances of each point in the element to the centroid.

If the least of these distances are greater than the distribution function value for the centroid:
Add the point/centroid to the list of candidate points.
Else
Set the element as unmodifiable.

Studies in Unstructured Grid Generation Using AFLR2E

2002-03-22T11:27:00.000-06:00

Note: This is a report written for a class I had in grad school in 2002. I found it using the Wayback Machine and decided that the algorithms alone were reason enough to keep it. The original report is provided here mainly for some semblance of context.

Methods

Centroid method

Given the algorithm's simplicity, the function wasn't too difficult to produce. The results, though, were a little disturbing, given the quality of results with more complex algorithms such as AF. This degree of difference defied explanation when trying to re-evaluate my code. I eventually gave up in favor of resignation to the fact that the AFLR2E code is probably more finely tuned (i.e. better choices for cdfn, etc.).

Circle	AFLR2E	Class
Number of Elements	542	536
Max Angle	113.114	112.302
Min Angle	23.19	23.19
Percent above 90 degrees	2.03	2.612
Percent below 30 degrees	14.945	14.925

Atlantic	AFLR2E	Class
Number of Elements	31116	41396
Max Angle	148.802	116.301
Min Angle	10.54	20.37
Percent above 90 degrees	15.834	0.469
Percent below 30 degrees	5.399	0.014

Advancing front method

This algorithm was much more complex, and as such, I had many more problems. But, in the end, it all worked out. Here are some results.

Atlantic	AFLR2E	Class
Number of Elements	41408	41408
Max Angle	116.301	116.301
Min Angle	20.37	20.37
Percent above 90 degrees	0.452	0.452
Percent below 30 degrees	0.017	0.017

As you can see, the results for the two are exactly the same. So, I would assume the algorithm is a success.

Also, here is an animated gif of my advancing front algorithm at work in the Gulf of Mexico.

Secondary Functions

Area Coordinate Search

This algorithm was not as difficult as the AF or the Global Check, but it proved to be a bit of a bear in the beginning.

This experiment involves using AFLR2E's fadd and fchk functions while toggling the srch function.

Atlantic	AFLR2E	Class
Number of Elements	41408	41408
Max Angle	116.301	116.301
Min Angle	20.37	20.37
Percent above 90 degrees	0.452	0.452
Percent below 30 degrees	0.017	0.017

Global Candidate Point Check

This algorithm was the oddest in testing. The differences seen in the AF algorithm below are unexplainable by me. I haven't the foggiest idea why the numbers are different (given how small the difference is).

This experiment involves using AFLR2E's fadd function and the class srch function (given no difference in performance) while toggling the fchk function.

Atlantic	AFLR2E	Class
Number of Elements	41408	41384
Max Angle	116.301	116.301
Min Angle	20.37	20.37
Percent above 90 degrees	0.452	0.462
Percent below 30 degrees	0.017	0.014

Conclusions

Regarding the centroid algorithm, I would have to assert from my findings that AFLR2E has a distinctive means of producing a centroid-type grid. From what I know about the algorithm in concept, my code should perform correctly (as it does for the most part). The differences in its results and that of AFRL2E's can only be accounted by a slight difference in approach (possibly a different node factor).

The advancing front algorithm seems to work quite well. Aside from being a (seemingly) robust tool, it also produces satisfying results. Its only down side is the computational cost. I can see that for very large fields, it might be prohibitive.

The two secondary functions were not difficult to produce, but "debugging" them got to be a bear, especially the global candidate point check. As stated above, the differences in AFLR2E's and my fchk functions are beyond my comprehension.