[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

# Re: [femm] triangle

- To: femm@yahoogroups.com
- Subject: Re: [femm] triangle
- From: David Meeker <dmeeker@foster-miller.com>
- Date: Mon, 15 Oct 2001 09:59:19 -0400
- Organization: Foster-Miller, Inc.
- References: <F30GA2kVrPm5QuG6kpa0000324e@hotmail.com>

you se-ho wrote:

> Is characteristic of banding matrix (and sparse matrix) inherent nature of
> finite element method from its matrix build-up regardless of what kind of
> mesh generation program is used? Does "renumbering
> methods" absolutely need to make matrix banding or does it just help to
> speed up the matrix calculation by making already banded matrix more banding?

It is the "inherent nature" of finite element methods that the resulting matrix is sparse. The reason that the matrices are sparse is that each node only "talks" to the nodes that are directly around it, leaving zeros in the matrix elements that correspond to direct interactions with nodes that are farther away. However, there is nothing in the formulation that automatically makes things banded. For example, if you just used a mesh straight out of Triangle and built your finite element matrix, you'd have a matrix that wasn't banded at all, although it would have a lot of zero entries. Now, iterative methods like Conjugate Gradient can work if you don't have a matrix with a nicely banded structure, but it makes a big difference if you are implementing a direct solver like Gauss Elimination without doing anything tricky. If you renumber your matrix carefully and take advantage of the banding to only allocate space for the entries inside the bandwidth, the size of the memory that you need to allocate to solve the problem is (I think roughly) on the order of n^(3/2), if you have n nodes in your matrix. If you just keep the full matrix, the number is n^2, which can be a huge difference for all but small problems. For direct methods, renumbering is usually the difference between being able to solve a problem and not being able to solve it at all. In contrast, iterative methods that are amenable to sparse matrix storage, where you only need to store the nonzero entries (you don't need any extra space for the algorithm to "work" in), need space on the order of n, which usually makes them more suitable for large problems.

Dave.

    begin:vcard
    n:Meeker;David
    tel;fax:781-890-3489
    tel;work:781-684-4070
    x-mozilla-html:TRUE
    url:http://members.aol.com/_ht_a/dcm3c
    org:Foster-Miller, Inc.;Electrical and Electronic Systems Group
    version:2.1
    email;internet:dmeeker@foster-miller.com
    title:Senior Engineer
    adr;quoted-printable:;;350 Second Avenue=0D=0A;Waltham;MA;02451-1196;USA
    fn:David Meeker, Ph.D.
    end:vcard

- References:
  - Re: [femm] triangle
    - From: "you se-ho" <sxy28@hotmail.com>

- Prev by Date: Re: triangle
- Next by Date: power factor
- Previous by thread: Re: [femm] triangle
- Next by thread: Re: [femm] triangle
- Index(es):
  - Date
  - Thread