Subject: [FFC-dev] Assembly speed

From: "Garth N. Wells" <[email-masked]>
Date: Tue, 22 Jul 2008 15:23:24 +0100

I've been testing assembly with various back-ends, and the bottleneck is 
std::map::insert(..). I don't see an easy away around this which would 
yield the complete sparsity pattern.

For various back-ends (PETSc, MTL4, and perhaps Trilinos), I would 
suggest that we go back to how we initialised matrices before the 
introduction of the sparsity pattern, where based on the number of 
neighbours to each cell and the finite element dimension, the maximum 
number of non-zeroes per row was estimated. With this information, there 
is no time overhead in assembling PETSc and MTL4 matrices relative to 
using the complete sparsity pattern.

A more sophisticated but complex approach would be to allow FFC to help 
compute the maximum number of non-zeroes. How hard would it be for FFC 
to compute the maximum number of non-zeroes per row given the number of 
neighbours of a mesh entity? Using FFC, it would be possible to take 
into account the type of finite element.

Garth

---

From: "Martin Sandve Alnæs" <[email-masked]>
Date: Tue, 22 Jul 2008 17:05:45 +0200

UFC 1.1 already has a function for tabulating the number of dofs
associated with each mesh entity, but I don't think FFC implements UFC
1.1 completely yet. Shouldn't this be all that's needed from FFC for
DOLFIN to compute/estimate the max non-zeroes per row? Sum the local
dimension of all elements and subtract the number of dofs for each
entity shared by neighbouring elements.

--
Martin

2008/7/22 Garth N. Wells <[email-masked]>:
> _______________________________________________
> DOLFIN-dev mailing list
> [email-masked]
> http://www.fenics.org/mailman/listinfo/dolfin-dev
>

---

From: Anders Logg <[email-masked]>
Date: Tue, 22 Jul 2008 17:42:21 +0200

On Tue, Jul 22, 2008 at 05:05:45PM +0200, Martin Sandve Alnæs wrote:
> 1.1 completely yet.

True. FFC does not yet implement tabulate_entity_dofs but it would be
fairly easy to add.

> Shouldn't this be all that's needed from FFC for

How should this be done? It seems that to do this, we would need to
compute all cell-cell connectivity which is fairly expensive. On the
other hand, we need to compute it anyway to initialize edges and
facets when there are dofs on those entities.

-- 
Anders

---

From: Anders Logg <[email-masked]>
Date: Tue, 22 Jul 2008 18:04:18 +0200

On Tue, Jul 22, 2008 at 10:49:47AM -0500, Matthew Knepley wrote:
> On Tue, Jul 22, 2008 at 10:42 AM, Anders Logg <[email-masked]> wrote:
> You can do it on the fly. I just use adj(c) = closure(start(c)). With a suitable
> global order, you can distinguish between diagonal and offdiagonal, and
> you are done.
> 
>   Matt

We can do something similar, but I haven't checked the cost of
computing the mesh connectivity compared to assembly.

Take piecewise linears for example. We just need the connectivity
D -- 0 (cells to vertices) to assemble. Investigating which dofs are
shared locally would require us to initialize/compute also D -- D.
But this is fairly cheap and O(N) so I guess it's something to
consider.

-- 
Anders