SparseDirectUMFPACK - member function "initialize" takes very long

[Simon]

Dear all,

I use the SparseDirectUMFPACK solver for doing some post-processing steps.

I also measure some cpu_times in my program in order to compare different methods regarding efficiency. For my question only the following three lines of code from my program are relevant:

---------------------------------------------------

timer.enter_section("Initialize Direct Solver");
sparse_direct_solver.initialize(global_matrix);
timer.leave_subsection("Initialize Direct Solver");

---------------------------------------------------

So I only measure the time which is neeed for executing the member function "initialize":

->Solving a scalar problem with dim=2 and 263425 DoFs the above call takes about 1.3 seconds, whereas solving the linear system takes only 0.8 seconds.

->Solving the same scalar problem with dim=3 and only 72369 DoFs the above call takes about 4.4 seconds and solving the linear system about 3.2 seconds.

-My first question is what this function actually does since it takes longer than assembling and solving the system together?

The documentation says: "This function does nothing. It is only here to provide a interface consistent with other sparse direct solvers."

By having a look in the function body I´ve seen that this function acutally does nothing, i.e. the function body is empty.

-My second question is why for my dim=3 case the function call takes much longer as in the dim=2 case? In the latter I have much more DoFs.

My guess was that the number of DoFs is the essential quantity but this is obviously not the case.

Any input would be greatly appreciated!

Best

Simon

[Praveen C]

The initialize function does the LU factorization which is the most expensive part

https://www.dealii.org/developer/doxygen/deal.II/classSparseDirectUMFPACK.html#af23a74dd9cac006c9d87c18e5d638076

The solution part should be faster than initialize.

Did you measure the time in “release” mode or “debug” ?

best

praveen

[Simon Wiesheier]

I failed to have a look at the wright function. So of couse this answers my first question.

I measure the times in release mode.

-Simon

--
The deal.II project is located at http://www.dealii.org/
For mailing list/forum options, see https://groups.google.com/d/forum/dealii?hl=en
---
You received this message because you are subscribed to the Google Groups "deal.II User Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/5B31FFA2-C446-41CD-A43E-9196A73B8269%40gmail.com.

[Wolfgang Bangerth]

On 6/2/21 8:26 AM, Simon wrote:
>
> -My second question is why for my dim=3 case the function call takes much
> longer as in the dim=2 case? In the latter I have much more DoFs.
> My guess was that the number of DoFs is the essential quantity but this is
> obviously not the case.

Sparse direct solvers need to form an elimination tree, and the work
associated with that is crucially determined by (i) the breadth of that tree ,
(ii) the number of entries per row. In 3d, you have substantially more entries
per row, and the breadth of the tree is larger. As a consequence, the
complexity of solving a linear system with a sparse direct solver is different
in 2d and 3d. See also the notes here:
https://www.math.colostate.edu/~bangerth/videos.676.34.html

In other words, sparse direct solvers are not nearly as attractive in 3d as
they are in 2d.

Best
W.

--
------------------------------------------------------------------------
Wolfgang Bangerth email: bang...@colostate.edu
www: http://www.math.colostate.edu/~bangerth/

[Abbas]

As for the second question. 
So the number of Dofs isn't the only predictor of how long an LU would take. 
Two things to note:
1) In 2D a single node is connected to 4 elements while in 3D a single node is connected to 8 elements which means that an unknown will show up in more equations which means that your matrix is less sparse now. This makes your LU more expensive to compute. 
2) Node numbering plays a role. I am not sure to what extent and I am not sure if it is something that is done automatically by direct solvers. Step-2 with it's Cuthill_McKee is something you might want to have a look at .

Best,
Abbas  

[Wolfgang Bangerth]

On 6/2/21 8:59 AM, Abbas wrote:
>
> 2) Node numbering plays a role. I am not sure to what extent and I am not sure
> if it is something that is done automatically by direct solvers. Step-2 with
> it's Cuthill_McKee

> <https://nam10.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.dealii.org%2Fcurrent%2Fdoxygen%2Fdeal.II%2FnamespaceDoFRenumbering.html%23ab938a690bf4e2adff191fe969b0f21d3&data=04%7C01%7CWolfgang.Bangerth%40colostate.edu%7Ca666a43196f746c74d5008d925d6fd84%7Cafb58802ff7a4bb1ab21367ff2ecfc8b%7C0%7C0%7C637582429206627171%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=FM0KPcJ7TmnahoGrINbqZBr1hL77L8tcSf9ri4DKsHI%3D&reserved=0> is

> something you might want to have a look at .

Yes, all direct solvers I know of renumber automatically. In the case of
UMFPACK, it uses the minimum-degree renumbering internally -- i.e., there is
no need to do that on the user side.

[Simon Wiesheier]

Thanks for all your answers!

It was my lack of mathematical background regarding solving linear systems which brought me to that question.

-Simon

--
The deal.II project is located at http://www.dealii.org/
For mailing list/forum options, see https://groups.google.com/d/forum/dealii?hl=en
---
You received this message because you are subscribed to the Google Groups "deal.II User Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/d1a526af-5945-48e4-b3a8-b9ba498b84f7%40colostate.edu.

[Simon Wiesheier]

One more question to the renumbering schemes: I called DoFRenumbering::Cuthill_McKee(dof_handler) before calling the initialize function of the direct solver.

So this isn´t really necessary when using UMFPACK because internally a different renumbering scheme is called anyway?

-Simon

[Wolfgang Bangerth]

On 6/2/21 10:16 AM, Simon Wiesheier wrote:
> One more question to the renumbering schemes: I called
> DoFRenumbering::Cuthill_McKee(dof_handler) before calling the initialize
> function of the direct solver.
>
> So this isn´t really necessary when using UMFPACK because internally a
> different renumbering scheme is called anyway?

Correct.

[Simon]

One more question came up when I watched your video "What solver to use". In there you mentioned that direct solvers in 2d have a complexity of O(N^2), where N is the number of unknowns.

There is an approximation for N, i.e.

N \approx p^d *|Omega| / h^d.

So from that can one say that solving a linear system with UMFPACK has a complexity of O(1/h^{4}) for a fixed degree p and d=2?

I ask that because I measured the times for solving two large linear systems in 2d, one with 1 Million DoFs and the other one with 2 Million DoFs (reducing h to h/2). The former took 11 seconds, the latter 110 seconds, i.e. they are related by a factor of 10 and not 16.

Backcalculating this, the factor of 10 would follow from a complexity of O(N^5/3}).

So is this is a plausible rate or is my linear system still not big enough to see the rate of 16? Is the renumbering scheme, which does UMFPACK internally, may the source why I see a lower rate?

Best

Simon

[Wolfgang Bangerth]

On 6/17/21 1:46 AM, Simon wrote:
> One more question came up when I watched your video "What solver to use". In
> there you mentioned that direct solvers in 2d have a complexity of O(N^2),
> where N is the number of unknowns.
> There is an approximation for N, i.e.
> N \approx p^d *|Omega| / h^d.
> So from that can one say that solving a linear system with UMFPACK has a
> complexity of O(1/h^{4}) for a fixed degree p and d=2?
> I ask that because I measured the times for solving two large linear systems
> in 2d, one with 1 Million DoFs and the other one with 2 Million DoFs (reducing
> h to h/2). The former took 11 seconds, the latter 110 seconds, i.e. they are
> related by a factor of 10 and not 16.
>
> Backcalculating this, the factor of 10 would follow from a complexity of
> O(N^5/3}).
> So is this is a plausible rate or is my linear system still not big enough to
> see the rate of 16? Is the renumbering scheme, which does UMFPACK internally,
> may the source why I see a lower rate?

The argument you make seems reasonable, but the rates I quote are for one
particular way of computing a sparse LU decomposition and, more importantly,
are *asymptotic*. You can't infer from just two data points what the rate is,
and it may well be possible that you can't ever observe the true rate of the
algorithm because you can't solve problems so large that the asymptotic rate
is attained.

Best