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. 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.
    5. Zhaolin Li & Artem Prokhorov, 2024. "Improved Semi-Parametric Bounds for Tail Probability and Expected Loss: Theory and Applications," Papers 2404.02400, arXiv.org, revised May 2025.
    6. 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.
    7. Joel Vanden, 2006. "Exact Superreplication Strategies for a Class of Derivative Assets," Applied Mathematical Finance, Taylor & Francis Journals, vol. 13(1), pages 61-87.
    8. Cai, Jun & Liu, Fangda & Yin, Mingren, 2024. "Worst-case risk measures of stop-loss and limited loss random variables under distribution uncertainty with applications to robust reinsurance," European Journal of Operational Research, Elsevier, vol. 318(1), pages 310-326.
    9. 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.
    10. 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.
    11. Schepper, Ann De & Heijnen, Bart, 2007. "Distribution-free option pricing," Insurance: Mathematics and Economics, Elsevier, vol. 40(2), pages 179-199, March.
    12. 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.
    13. 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.
    14. Li, Minqiang, 2008. "Closed-Form Approximations for Spread Option Prices and Greeks," MPRA Paper 6994, University Library of Munich, Germany.
    15. Carole Bernard & Silvana M. Pesenti & Steven Vanduffel, 2024. "Robust distortion risk measures," Mathematical Finance, Wiley Blackwell, vol. 34(3), pages 774-818, July.
    16. Villegas, Andrés M. & Medaglia, Andrés L. & Zuluaga, Luis F., 2012. "Computing bounds on the expected payoff of Alternative Risk Transfer products," Insurance: Mathematics and Economics, Elsevier, vol. 51(2), pages 271-281.
    17. Chung, Kee H. & Smith, William T. & Wu, Tao L., 2009. "Time diversification: Definitions and some closed-form solutions," Journal of Banking & Finance, Elsevier, vol. 33(6), pages 1101-1111, June.
    18. Kirschner, Felix, 2023. "Conic optimization with applications in finance and approximation theory," Other publications TiSEM e9bef4a5-ee46-45be-90d7-9, Tilburg University, School of Economics and Management.
    19. Laurence, Peter & Wang, Tai-Ho, 2009. "Sharp distribution free lower bounds for spread options and the corresponding optimal subreplicating portfolios," Insurance: Mathematics and Economics, Elsevier, vol. 44(1), pages 35-47, February.
    20. Dimitris Bertsimas & Ioana Popescu, 2002. "On the Relation Between Option and Stock Prices: A Convex Optimization Approach," Operations Research, INFORMS, vol. 50(2), pages 358-374, April.

    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.