scipy.linalg.solveh_bandedのソースを見ると、Lapackpbsvをラップしているだけです。Lapack ptsv関数によって提供されるはずの三重対角（エルミート、または私の場合は実際の対称）システム用のより効率的なソルバーを探しています。さらに、これは実際の問題ではないはずですが、主対角線に沿った（すべて正の）値のダイナミックレンジが大きすぎると、solveh_bandedがクラッシュします（丸めによって最小値が事実上負に見えるようになると思いますので、負の固有値を持っていると見なされます）、三重対角固有のルーチンがこの問題にヒットしない可能性があります。
Lapackについての私の読書から、ptsvはpbsvを持つすべてのディストリビューションに含まれるべきであるように思われます（ドキュメントは常にそれらを一緒にリストします）。どちらがより効率的かはわかりませんが（pbsvは対称であるが任意の帯域幅であると想定し、ptsvは三重対角であるが必ずしも対称であるとは想定していません）、ptsvを試す価値があるようです。
残念ながら、ptsvはscipyに公開されていないようです。これは、実際にはscipy.linalg.flapackに含まれていないため、scipy.linalg.get_lapack_funcs（（'ptsv'、））からは利用できないことを意味します。
scipyとのFortran/Lapackのリンクは複雑であることに気づきましたが、pbsvとptsvの扱いが異なる理由を誰かが知っていますか？pbsvのようにptsvをラップするために手動で編集できるものはありますか（残念ながら、flapackは「.so」として提供されているようで、行き止まりになりました）。
FWIWIntelMKLでEnthoughtEPDを使用しています。ただし、scipy.linalg（分布に依存しない）には常にsolveh_bandedが含まれていますが、三重対角ソルバーがないことを考えると、EPD/MKLの問題よりも深くなければならないと思います。