Re: [deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-17 Thread 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
 W.

--

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

--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/bb76b031-e608-e650-5ba4-155d8ea8f091%40colostate.edu.

Re: [deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-17 Thread 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 schrieb am Mittwoch, 2. Juni 2021 um 18:21:56 UTC+2:

> 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.
> W.
>
>
> -- 
> 
> Wolfgang Bangerth email: bang...@colostate.edu
> www: http://www.math.colostate.edu/~bangerth/
>
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/168e3b0a-5860-4c0a-9d70-4639d13e63a1n%40googlegroups.com.

Re: [deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-02 Thread 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.
W.


--

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

--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/49aa8c13-2ab2-ad1e-4f4d-6021e76fb0db%40colostate.edu.

Re: [deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-02 Thread 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

Am Mi., 2. Juni 2021 um 17:16 Uhr schrieb Simon Wiesheier <
simon.wieshe...@gmail.com>:

> Thanks for all your answers!
> It was my lack of mathematical background regarding solving linear systems
> which brought me to that question.
>
> -Simon
>
> Am Mi., 2. Juni 2021 um 17:09 Uhr schrieb Wolfgang Bangerth <
> bange...@colostate.edu>:
>
>> 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.
>>
>> Best
>>   W.
>>
>> --
>> 
>> Wolfgang Bangerth  email: bange...@colostate.edu
>> www: http://www.math.colostate.edu/~bangerth/
>>
>> --
>> 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+unsubscr...@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/dealii/d1a526af-5945-48e4-b3a8-b9ba498b84f7%40colostate.edu
>> .
>>
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/CAM50jEtuqJuvrWSj9gYLLXQ5zgd-%2B6bGCD2hC9u%2BBBMnmuA02g%40mail.gmail.com.

Re: [deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-02 Thread 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

Am Mi., 2. Juni 2021 um 17:09 Uhr schrieb Wolfgang Bangerth <
bange...@colostate.edu>:

> 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.
>
> Best
>   W.
>
> --
> 
> Wolfgang Bangerth  email: bange...@colostate.edu
> www: http://www.math.colostate.edu/~bangerth/
>
> --
> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/dealii/d1a526af-5945-48e4-b3a8-b9ba498b84f7%40colostate.edu
> .
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/CAM50jEtvH0_JOzqA_vu4c9imDDajwAvvBVSy1HYcPgWg1wQFpw%40mail.gmail.com.

Re: [deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-02 Thread 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 
 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.


Best
 W.

--

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

--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/d1a526af-5945-48e4-b3a8-b9ba498b84f7%40colostate.edu.

[deal.II] Re: SparseDirectUMFPACK - member function "initialize" takes very long

2021-06-02 Thread 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  
On Wednesday, June 2, 2021 at 10:26:29 AM UTC-4 Simon wrote:

> 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
>
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/dealii/e35b5222-a735-4678-8418-4f5d72d76627n%40googlegroups.com.