A fast algorithm for computing the determinants of banded circulant matrices

Let Cn be a (k+1)-diagonal complex circulant matrix of order n(≥k+1), and let detCn be the determinant of Cn. An algorithm for computing detCn is presented with the cost of Oklog2k·log2n+k4 multiplication, and an asymptotic formula for detCn is obtained. Moreover, a result on symmetric circulant matrices with integer entries is also given. Using Mathematica in a personal computer, we give some numerical examples, which illustrate that the algorithm is very efficient and the asymptotic formula is accurate enough when the order n of the circulant matrix is sufficiently large.