Tene,What is the rationale for the relationship between NS and NT (5:1 approx).Smax = 4 * K. edit: had a look at the Bren/Sch algo. Basically, one uses CN(for example) and modified LU to take early exercise constraint. This is almost the same as my scheme except I have explicit in time ADE. LU is not needed.

QuoteI'd be delighted to see the proof that this method gives the optimal priceHere's my hunch. I refer to your paper.1. Instead of (2.9) based on theta method, and the resulting (2.13) use ADE sweeps and apply (2.13) to each sweep solution. Then average them. A kind of reverse engineering. 2. You probably end up with simpler matrices in 2.13 (A and/or B)3. Rannacher CN is better than CN but not 100% water-tight. Wiggles possible.4. Equation (2.13) etc. for 2 factor model..Quote Nonuniform grids make the implementation a bit more complicated,but they also improve accuracy.I never use NUGs in space. Why are they needed?The whole point of fitted schemes is that coarse uniform grids model boundary layers and spikes. edit: In PSOR, instead of CN if I use explicit, then the inequality (v - g).(Cv - b) = 0 etc. becomes almost trivial because C == Identity matrix. I think this approach is scalable..

QuoteOriginally posted by: CuchulainnQuoteI'd be delighted to see the proof that this method gives the optimal priceHere's my hunch. I refer to your paper.1. Instead of (2.9) based on theta method, and the resulting (2.13) use ADE sweeps and apply (2.13) to each sweep solution. Then average them. A kind of reverse engineering. 2. You probably end up with simpler matrices in 2.13 (A and/or B)3. Rannacher CN is better than CN but not 100% water-tight. Wiggles possible.4. Equation (2.13) etc. for 2 factor model..1. Optimality. So, you got two optimal solutions! And then you do average them, don't you? The BS price is unique and your algorithm assumes otherwise! AOPT algorithm makes local updates of the solution and is exactly optimal at each step.2. Accuracy. If you rely on one of the solutions, then this is conceputally sound, but without averaging ADE is a first order scheme. AOPT is second order accurate.3. Complexity. At each time step, AOPT starts from the previous solution and performs local LU updates from step to step. Hence, in total, AOPT does one and only one LU decomposition, which is very cheap for tridiagonal matrices. This has to be compared to the total of forward and backward substitutions that ADE makes at each step!

Quote1. Optimality. So, you got two optimal solutions! And then you do average them, don't you? The BS price is unique and your algorithm assumes otherwise! AOPT algorithm makes local updates of the solution and is exactly optimal at each step.I have two *partial* solutions; sweep 1 is from S = 0 and sweep 2 is from S = Smax. I dosweep 1checksweep 2checkaverage to get both BCs in final solution.See my experimental results. This does not work:sweep 1sweep 2average to get both BCs in final solution.checkQuote2. Accuracy. If you rely on one of the solutions, then this is conceputally sound, but without averaging ADE is a first order scheme. AOPT is second order accurate.Nope, Each solution is a partial solution.Actually, sweeps are O(k/h) (!!) accurate but average is O(k^2 + h^2). So, ADE is second order which is well-known.Quote3. Complexity. At each time step, AOPT starts from the previous solution and performs local LU updates from step to step. Hence, in total, AOPT does one and only one LU decomposition, which is very cheap for tridiagonal matrices. This has to be compared to the total of forward and backward substitutions that ADE makes at each step! LU and ADE as equally fast on single core, indeed. With ADE I scrap all the LU code. Throw in 2 OpenMP pragma stuff ==> speedup 1.6. And ADE in n factors is easy.

QuoteOriginally posted by: CuchulainnQuote1. Optimality. So, you got two optimal solutions! And then you do average them, don't you? The BS price is unique and your algorithm assumes otherwise! AOPT algorithm makes local updates of the solution and is exactly optimal at each step.I have two *partial* solutions; sweep 1 is from S = 0 and sweep 2 is from S = Smax. I dosweep 1checksweep 2checkaverage to get both BCs in final solution.See my experimental results.This is what I meant: the average of two optimal *partial* solutions is NOT an optimal solution. Your prices may loose some residual option leverage to the holder, overestimating the price for the writer.Quote2. Accuracy. If you rely on one of the solutions, then this is conceputally sound, but without averaging ADE is a first order scheme. AOPT is second order accurate.Nope, Each solution is a partial solution.Actually, sweeps are O(k/h) (!!) accurate but average is O(k^2 + h^2). So, ADE is second order which is well-known.Your scheme averages "sweep+check" steps, so O(k/h) remains whenever the check reveals the stopping prices. So the overall scheme is first order.Quote3. Complexity. At each time step, AOPT starts from the previous solution and performs local LU updates from step to step. Hence, in total, AOPT does one and only one LU decomposition, which is very cheap for tridiagonal matrices. This has to be compared to the total of forward and backward substitutions that ADE makes at each step! LU and ADE as equally fast on single core, indeed. With ADE I scrap all the LU code. Throw in 2 OpenMP pragma stuff ==> speedup 1.6. And ADE in n factors is easy.One LU against many (the total number of time steps) backward+forward susbstitutions is much more faster, hence AOPT is faster than ADE.

QuoteYour prices may loose some residual option leverage to the holder, overestimating the price for the writer.Can you explain this? I get the same results as compared with *all* other methods, so what am I missing here?QuoteOne LU against many (the total number of time steps) backward+forward susbstitutions is much more faster, hence AOPT is faster than ADE. I tested implicit Euler vs ADE. I got similar response times. But it's not on the critical path.If you could take tene's benchmark and post your new results would be useful. Unfortunately, your article does not contain any prices, just error estimates.

QuoteOriginally posted by: CuchulainnQuoteYour prices may loose some residual option leverage to the holder, overestimating the price for the writer.Can you explain this? I get the same results as compared with *all* other methods, so what am I missing here?For your scheme to be ok the sum of two max functions on two ADE halves should give the max of the LU full price. Do you have a rigorous proof? Benchmarks for a set of given option parameters are indeed useful, but they are no guarantee that the same holds in the whole range of the parameter space. That is why a rigorous result is needed.

QuoteOriginally posted by: boriciQuoteOriginally posted by: CuchulainnQuoteYour prices may loose some residual option leverage to the holder, overestimating the price for the writer.Can you explain this? I get the same results as compared with *all* other methods, so what am I missing here?For your scheme to be ok the sum of two max functions on two ADE halves should give the max of the LU full price. Do you have a rigorous proof? Benchmarks for a set of given option parameters are indeed useful, but they are no guarantee that the same holds in the whole range of the parameter space. That is why a rigorous result is needed.Is LU special in this case? It's just the Brennan Schwarz check. A rigorous approach would be nice, indeed. I have 6 test cases in my article over all parameters for Europeans. Test VI is early exercise that I did to see if it works. And it did for the test cases. The numerical analysis for European options is also done. O(k^2 + h^2).A theoretical numerical analysis is a good idea, but I am not in a uni anymore, so making time for this interesting project is difficult. BTW I have it for Euler and LU, but that's well known. Could be a nice student project...Will you post your numbers, or not? I am trying to make some progress here and feedback is very welcome. Thanks.

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: boriciQuoteOriginally posted by: CuchulainnQuoteYour prices may loose some residual option leverage to the holder, overestimating the price for the writer.Can you explain this? I get the same results as compared with *all* other methods, so what am I missing here?For your scheme to be ok the sum of two max functions on two ADE halves should give the max of the LU full price. Do you have a rigorous proof? Benchmarks for a set of given option parameters are indeed useful, but they are no guarantee that the same holds in the whole range of the parameter space. That is why a rigorous result is needed.Is LU special in this case? It's just the Brennan Schwarz check. A rigorous approach would be nice, indeed. I have 6 test cases in my article over all parameters for Europeans. Test VI is early exercise that I did to see if it works. And it did for the test cases. The numerical analysis for European options is also done. O(k^2 + h^2).A theoretical numerical analysis is a good idea, but I am not in a uni anymore, so making time for this interesting project is difficult. BTW I have it for Euler and LU, but that's well known. Could be a nice student project...Will you post your numbers, or not? I am trying to make some progress here and feedback is very welcome. Thanks.Sure! I'll try to find some time in a couple of days. Indeed, it is important to see the price difference.

Thanks. Let's take tene's benchmark. Quote1. Optimality. So, you got two optimal solutions! And then you do average them, don't you? The BS price is unique and your algorithm assumes otherwiseRight, got itNow I do the exercise on the 'real' solution 'u' but not on U and B at each time level:1. Compute U, V2. u = (U+V)/23. Check (u)4. U = u , V = u for next time level(remark: steps 2 and 3 is what you probably do in your 'LU step').Benchmark answer from tene was 3.0700463 For same steps as tene I get {2.89596, 3.051706, 3.08829, 3.098484, 3.079997, 3.064416}Since I use fits and ADE works best like k/h -> 0 uniformly (I use uniform meshes)100, 100, P = 3.004476200,200, P = 3.059068300,300, P = 3.070758400,400, P = 3.072222500, 500, P = 3.070198600,600, P = 3.070552700,7000, P = 3.0706833000, 4000, P = 3.070456Looks more even than first strategy. So, we wortk with correct BS at each time level.

The Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.

QuoteOriginally posted by: CuchulainnThe Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.The Brennan-Schwarz algorithm has the same problem with the optimality. See the book "American put options", D. M. Salopek, p93 concludes that "the lagorithm itself leads to a false solution".

QuoteOriginally posted by: boriciQuoteOriginally posted by: CuchulainnThe Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.The Brennan-Schwarz algorithm has the same problem with the optimality. See the book "American put options", D. M. Salopek, p93 concludes that "the lagorithm itself leads to a false solution".That's an expensve book!!!! Does Salek say why? IE is a first-order scheme, so that's what we expected. Is there some other hidden meaning?

QuoteOriginally posted by: CuchulainnThe Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.Here are the AOPT results with your results included:time space timesteps steps price error in ms ADE AOPT 10 40 3.0106496 -5.9e-02 0.1 2.89596 3.0401021 18 80 3.0553799 -1.5e-02 0.3 3.051706 3.0622096 34 160 3.0663983 -3.7e-03 0.9 3.08829 3.0678056 66 320 3.0691617 -9.5e-04 3.6 3.098484 3.0693869130 640 3.0698666 -2.4e-04 14.2 3.079997 3.0698641258 1280 3.0700463 -6.0e-05 57.2 3.064416 3.0700170 ADE IE Brennan Schwartz AOPT 100 100 3.004476 2.97486 3.0651129 200 200 3.059068 3.04 3.0688161 300 300 3.070758 3.060636 3.0695117 400 400 3.072222 3.06462 3.0697638 500 500 3.070198 3.064269 3.0698829 600 600 3.070552 3.06568 3.0699491 700 7000 3.070683 3.066568 3.06984363000 4000 3.070456 xxxxxxxx 3.07010027000 700 xxxxxxx xxxxxxxx 3.07000334000 3000 xxxxxxx xxxxxxxx 3.0700987I hope you appreciate the difference

QuoteOriginally posted by: boriciQuoteOriginally posted by: CuchulainnThe Brennan Schwarz algo using Implicit Euler, LU and the standard check100, 100, P = 2.97486200,200, P = 3.04300,300, P = 3.060636400,400, P = 3.06462500, 500, P = 3.064269600,600, P = 3.06568700,7000, P = 3.0665683500, 3500, P = 3.0696654000,4000, P = 3.070014 (ADE needs 300X300)It's clear, yes?So, a numerical analysis in general is just a variation of the standard approach.I look forward to AOPT performance results.Here are the AOPT results with your results included:time space timesteps steps price error in ms ADE AOPT 10 40 3.0106496 -5.9e-02 0.1 2.89596 3.0401021 18 80 3.0553799 -1.5e-02 0.3 3.051706 3.0622096 34 160 3.0663983 -3.7e-03 0.9 3.08829 3.0678056 66 320 3.0691617 -9.5e-04 3.6 3.098484 3.0693869130 640 3.0698666 -2.4e-04 14.2 3.079997 3.0698641258 1280 3.0700463 -6.0e-05 57.2 3.064416 3.0700170 ADE IE Brennan Schwartz AOPT 100 100 3.004476 2.97486 3.0651129 200 200 3.059068 3.04 3.0688161 300 300 3.070758 3.060636 3.0695117 400 400 3.072222 3.06462 3.0697638 500 500 3.070198 3.064269 3.0698829 600 600 3.070552 3.06568 3.0699491 700 7000 3.070683 3.066568 3.06984363000 4000 3.070456 xxxxxxxx 3.07010027000 700 xxxxxxx xxxxxxxx 3.07000334000 3000 xxxxxxx xxxxxxxx 3.0700987I hope you appreciate the difference