curse of dimensionality persists

curse of dimensionality persists

Postby cppljevans » Sat Sep 10, 2011 1:03 am

In http://www.datasimfinancial.com/forum/d ... php?id=351

which is the PDEADE.pdf file, there's mention of the "curse of

dimensionality; however, in the 3D code shown in that paper,

there are two nested loops of depth 3. If the dimension is

changed then the depth of those loops must change; hence,

there's still some "curse" left.



One way to solve that is demonstrated in the attached prototype

code. If you interested, I could develop it further so that

it could be used in the problem shown in PDEADE.pdf.
Attachments
index_stack_simple.cpp
Shows how nested for loops can be flattened.
(2.63 KiB) Downloaded 616 times
index_stack_simple.txt
output from .cpp attachment
(2.62 KiB) Downloaded 608 times
cppljevans
 
Posts: 14
Joined: Thu Jun 30, 2011 5:31 pm

Postby cppljevans » Fri Sep 23, 2011 8:55 pm

The just uploaded file:



http://svn.boost.org/svn/boost/sandbox/ ... e.crtp.cpp



illustrates a solution to the remaining "curse of dimensionality"

problem using a class derived from the index_stack_simple.hpp

previously uploaded in my previous post. The output shows

%error compared to what I think is the exact solution. The output

shows about .02% error in last of 2916 iterations.



Any feedback welcome.



-regards,

Larry
cppljevans
 
Posts: 14
Joined: Thu Jun 30, 2011 5:31 pm

Postby Cuchulainn » Mon Oct 10, 2011 10:52 am

In the sense that there are hard-coded loops, yes. Bit multiarray can also handle more general iterators, at the cost of readability.



Using variadics with FDM would be unique.
User avatar
Cuchulainn
 
Posts: 677
Joined: Mon Dec 18, 2006 2:48 pm
Location: Amsterdam, the Netherlands

Postby cppljevans » Mon Oct 10, 2011 3:59 pm

Cuchulainn wrote:In the sense that there are hard-coded loops, yes. Bit multiarray can also handle more general iterators, at the cost of readability.



Using variadics with FDM would be unique.




Based on a brief look at:



http://www.boost.org/doc/libs/1_47_0/li ... rators.cpp



it appears that the multi_array iterators apply to only one dimension.



OTOH, the template



index_stack_length_stride_crtp_indices



from:



http://svn.boost.org/svn/boost/sandbox/ ... e_crtp.hpp



stores, in essence, a stack of iterators. This stack of

iterators just stores the same information as the begin/end iterators

in the nested loops of:



http://www.boost.org/doc/libs/1_47_0/li ... rators.cpp



and, increments or decrements the appropriate iterators when

the operator++ or operator-- is called.



The advantage of index_stack_length_stride_crtp.hpp

is that it's dimension independent whereas the code in

iterators.cpp is not. IOW, if, instead of the multi_array being

dimension 3 it had a dimension 4, the the code in

iterators.cpp would have to add an iterator4 and then nest

the existing 3 loops with another outer loop using that iterator4.
cppljevans
 
Posts: 14
Joined: Thu Jun 30, 2011 5:31 pm

ADI in addition to ADE in boost sandbox

Postby cppljevans » Fri Oct 28, 2011 3:47 pm

cppljevans wrote:The just uploaded file:



http://svn.boost.org/svn/boost/sandbox/ ... e.crtp.cpp



illustrates a solution to the remaining "curse of dimensionality"

problem using a class derived from the index_stack_simple.hpp

previously uploaded in my previous post. The output shows

%error compared to what I think is the exact solution. The output

shows about .02% error in last of 2916 iterations.



Any feedback welcome.



-regards,

Larry




I've replaced the array_dyn.ade.crtp.cpp with

array_dyn.diff_pde.cpp. The replacement adds

the ADI method from section 19.5 of

http://www.amazon.com/Finite-Difference ... 0470858826



However, as noted here:



http://article.gmane.org/gmane.comp.lib ... user/71047



I'm worried about the error of ADI compared with the ADE

method. The large ADI error relative to ADE suggests

I've made some error in the ADI implementation.

The TRACE_* macros in the solve_tridiag.hpp help

show what's happening; however, I still can't

figure out where there could be a bug.



Any feedback is welcome.



-kind regards,

Larry
cppljevans
 
Posts: 14
Joined: Thu Jun 30, 2011 5:31 pm

Postby Cuchulainn » Sat Oct 29, 2011 9:28 pm

Larry,

Sorry for delay. Which PDE are you solving ADI in section 19.5? Do you have mixed derivatives.



ADI is bad, well no always good. Long story; if you like to ring me feel free.



I do not think it's your code but ADI itself.



regards



Daniel
User avatar
Cuchulainn
 
Posts: 677
Joined: Mon Dec 18, 2006 2:48 pm
Location: Amsterdam, the Netherlands

Postby Cuchulainn » Sat Oct 29, 2011 9:35 pm

One thing that worries me is that the relative error for ADI is about 10x what the relative error for ADE. I've not yet figured out why :(



Much is known about deficiencies of ADI see wilmott.com forum



I never use it now, either Soviet Splitting or ADE.



hth



Daniel
User avatar
Cuchulainn
 
Posts: 677
Joined: Mon Dec 18, 2006 2:48 pm
Location: Amsterdam, the Netherlands

Postby cppljevans » Sat Oct 29, 2011 9:58 pm

Cuchulainn wrote:Larry,

Sorry for delay. Which PDE are you solving ADI in section 19.5? Do you have mixed derivatives.



ADI is bad, well no always good. Long story; if you like to ring me feel free.



I do not think it's your code but ADI itself.



regards



Daniel




Thanks for the ( what I'd consider) a fast response.



The PDE I'm solving is the the heat equation where the exact solution

is the fundamental solution. For the boundary conditions, I simply

use the exact solution. the comments in the exact_indices

function within fundamental<?>::soln<double> contain the

references. Since it's the heat equation, there's no mixed

derivatives. Since the 1st paragraph of section 19.5 says:



if there is an uneven number of legs we will get unstable schemes!



I made sure to just test an even number of dimensions.



Thanks for the ring offer. I'll still try to figure out what may be

wrong and if I can't, Ill give you a call.



Thanks again.



-kind regards,

Larry
cppljevans
 
Posts: 14
Joined: Thu Jun 30, 2011 5:31 pm


Return to Finite Difference Methods

Who is online

Users browsing this forum: No registered users and 1 guest

cron