A fast algorithm for evaluating nth order tri-diagonal determinants

摘要

The cost of all existing algorithms for evaluating the nth order determinants (Numerical Analysis, 7th Edition, Brooks & Cole Publishing, Pacific Grove, CA, 2001) is at most O(n3). In the current article we present a new efficient computational algorithm for evaluating the nth order tri-diagonal determinants with cost O(n) only. The algorithm is suited for implementation using Computer Algebra Systems such as MAPLE and MACSYMA. Some examples are given to illustrate the algorithm.