IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1402.5094.html
   My bibliography  Save this paper

Accelerating Implicit Finite Difference Schemes Using a Hardware Optimized Tridiagonal Solver for FPGAs

Author

Listed:
  • Samuel Palmer

Abstract

We present a design and implementation of the Thomas algorithm optimized for hardware acceleration on an FPGA, the Thomas Core. The hardware-based algorithm combined with the custom data flow and low level parallelism available in an FPGA reduces the overall complexity from 8N down to 5N serial arithmetic operations, and almost halves the overall latency by parallelizing the two costly divisions. Combining this with a data streaming interface, we reduce memory overheads to 2 N-length vectors per N-tridiagonal system to be solved. The Thomas Core allows for multiple independent tridiagonal systems to be continuously solved in parallel, providing an efficient and scalable accelerator for many numerical computations. Finally we present applications for derivatives pricing problems using implicit finite difference schemes on an FPGA accelerated system and we investigate the use and limitations of fixed-point arithmetic in our algorithm.

Suggested Citation

  • Samuel Palmer, 2014. "Accelerating Implicit Finite Difference Schemes Using a Hardware Optimized Tridiagonal Solver for FPGAs," Papers 1402.5094, arXiv.org, revised Oct 2015.
    • Handle: RePEc:arx:papers:1402.5094
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1402.5094
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Lo, Andrew W., 1987. "Semi-parametric upper bounds for option prices and expected payoffs," Journal of Financial Economics, Elsevier, vol. 19(2), pages 373-387, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Javier Pena & Juan Vera & Luis Zuluaga, 2010. "Static-arbitrage lower bounds on the prices of basket options via linear programming," Quantitative Finance, Taylor & Francis Journals, vol. 10(8), pages 819-827.
    2. Donald J. Brown & Rustam Ibragimov, 2005. "Sign Tests for Dependent Observations and Bounds for Path-Dependent Options," Cowles Foundation Discussion Papers 1518, Cowles Foundation for Research in Economics, Yale University.
    3. Lim, Terence & Lo, Andrew W. & Merton, Robert C. & Scholes, Myron S., 2006. "The Derivatives Sourcebook," Foundations and Trends(R) in Finance, now publishers, vol. 1(5–6), pages 365-572, April.
    4. repec:dau:papers:123456789/30 is not listed on IDEAS
    5. Roy H. Kwon & Jonathan Y. Li, 2016. "A stochastic semidefinite programming approach for bounds on option pricing under regime switching," Annals of Operations Research, Springer, vol. 237(1), pages 41-75, February.
    6. Ryan, Peter J., 2003. "Progressive option bounds from the sequence of concurrently expiring options," European Journal of Operational Research, Elsevier, vol. 151(1), pages 193-223, November.
    7. Liu, Guoqing & Li, Wenbo V., 2009. "Moment bounds for truncated random variables," Statistics & Probability Letters, Elsevier, vol. 79(18), pages 1951-1956, September.
    8. Li Chen & Simai He & Shuzhong Zhang, 2011. "Tight Bounds for Some Risk Measures, with Applications to Robust Portfolio Selection," Operations Research, INFORMS, vol. 59(4), pages 847-865, August.
    9. Li Zhang & Norma Nielson, 2012. "Pricing for Multiline Insurer: Frictional Costs, Insolvency, and Asset Allocation," Risk Management and Insurance Review, American Risk and Insurance Association, vol. 15(2), pages 129-152, September.
    10. Jinfeng Yue & Bintong Chen & Min-Chiang Wang, 2006. "Expected Value of Distribution Information for the Newsvendor Problem," Operations Research, INFORMS, vol. 54(6), pages 1128-1136, December.
    11. Joel Vanden, 2006. "Exact Superreplication Strategies for a Class of Derivative Assets," Applied Mathematical Finance, Taylor & Francis Journals, vol. 13(1), pages 61-87.
    12. Donald Brown & Rustam Ibragimov, 2005. "Sign Tests for Dependent Observations and Bounds for Path-Dependent Options," Yale School of Management Working Papers amz2581, Yale School of Management, revised 01 Jul 2005.
    13. Roy Kwon & Jonathan Li, 2016. "A stochastic semidefinite programming approach for bounds on option pricing under regime switching," Annals of Operations Research, Springer, vol. 237(1), pages 41-75, February.
    14. Dimitris Bertsimas & Aurélie Thiele, 2006. "A Robust Optimization Approach to Inventory Theory," Operations Research, INFORMS, vol. 54(1), pages 150-168, February.
    15. DeMarzo, Peter M. & Kremer, Ilan & Mansour, Yishay, 2016. "Robust option pricing: Hannan and Blackwell meet Black and Scholes," Journal of Economic Theory, Elsevier, vol. 163(C), pages 410-434.
    16. Didier Henrion & Felix Kirschner & Etienne De Klerk & Milan Korda & Jean-Bernard Lasserre & Victor Magron, 2023. "Revisiting Semidefinite Programming Approaches to Options Pricing: Complexity and Computational Perspectives," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 335-349, March.
    17. Boyle, Phelim P. & Lin, X. Sheldon, 1997. "Bounds on contingent claims based on several assets," Journal of Financial Economics, Elsevier, vol. 46(3), pages 383-400, December.
    18. Schepper, Ann De & Heijnen, Bart, 2007. "Distribution-free option pricing," Insurance: Mathematics and Economics, Elsevier, vol. 40(2), pages 179-199, March.
    19. Zuluaga, Luis F. & Peña, Javier & Du, Donglei, 2009. "Third-order extensions of Lo's semiparametric bound for European call options," European Journal of Operational Research, Elsevier, vol. 198(2), pages 557-570, October.
    20. Derek Singh & Shuzhong Zhang, 2020. "Tight Bounds for a Class of Data-Driven Distributionally Robust Risk Measures," Papers 2010.05398, arXiv.org, revised Oct 2020.
    21. Li, Minqiang, 2008. "Closed-Form Approximations for Spread Option Prices and Greeks," MPRA Paper 6994, University Library of Munich, Germany.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:1402.5094. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.