Finite element method: Difference between revisions

Revision as of 17:24, 27 January 2004

Revision as of 17:30, 27 January 2004

Line 90:

\phi_v\left(\mathrm{L}u\right)=\phi_v\left(g\right)

</math>

:&phi;_''v''(L''u'')=&phi;_''v''(''g'')

for all ''v'' in V. From now on, we will use &int;_T for the double integral &int;₀¹&int;₀¹. One can see, via [[integration by parts]], and noting that because of the periodic boundary condition the first right hand side ''fg'' term

Line 148 ⟶ 146:

The astute reader will have noted that the last problem can be formulated as a [[matrix]] problem as follows:

:<math>

:P''a''=Q''b''

\mathrm{P}a=\mathrm{Q}b

</math>

where ''a'' is the column vector (a1,a2,...,an) and ''b'' is the column vector (b1,b2,...,bn). The matrices P and Q are given by (***):

Line 175:

To obtain better algorithms, one can attempt to vary the primitives of the tesselation; it may be more natural to use rectangular elements, and in some cases curvilinear elements are called for. Conversely, once the elements are chosen, one still has a choice of how to define the test functions on each element. Test functions are usually, but not always chosen to be piecewise polynomial.

If the test functions are chosen in a cunning way, the matrices P and Q will be structured so that the linear problem Pa=Qb can be solved very quickly. To understand the problem here, the calculation of Qb requires apparently O(n^²) multiplications and additions. However, if one chooses the Fourier basis, one notes that Q is the identity matrix, so there's nothing to be done to compute Qb. The coefficients of b can then be found using the fast fourier transform of g, which runs in O(nlogn) time. The matrix P is diagonal with easily calculated entries, so solving for a is trivial. One would then typically do an inverse Fourier transform on a, which requires O(nlogn) to obtain u.

If one chooses a finite element basis (using, for instance, the triangular elements discussed above) so that each test function is supported on a small number of elements then one can see that the matrices P and Q will be ''sparse'' -- that is, most of the entries are zero. Then the calculation Qb can be done in O(n) time, and solving for a can be done efficiently using an iterative algorithm (such as the [[Conjugate gradient iteration]]).