[fakesson]

"High Performance American Option Pricing" by Leif Andersen et al is many orders of magnitude faster than any finite difference method or other PDE / tree method. https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2547027

Given the exercise boundary, the American Option Price can be written exactly as a one-dimensional integral. That is the key insight to this superior method.

[scott00]

Is that method extensible to discrete dividends?

[fakesson]

I googled and found slides there Leif extends the method to discrete dividends: https://www.math.cmu.edu/CCF/CCFevents/shreve/abstracts/L.An...

( I'm a fixed income quant, so I didn't look for it until now.) For a more advance model than Black-Scholes, e.g. local vol I don't expect it can be extended, and one would then need use some PDE based method.