On 3/10/14, Joerg Arndt <arndt@jjj.de> wrote:
* Warren D Smith <warren.wds@gmail.com> [Mar 10. 2014 07:22]:
[...]
For Toeplitz matrices, there should be FFT methods.
Can you say a bit more about how this would work? Hankel determinants (of Toeplitz matrices) can be evaluated via what Conway & Guy christened the "wall of numbers" in their "Book of Numbers". This algorithm copes with zeros in the table, making it applicable also to finite field computations --- the |F_2 case is particularly simple. Or at least it would cope, if it weren't for a couple of nasty misprints noticed by Jim Propp; for the correct version see https://cs.uwaterloo.ca/journals/JIS/VOL4/LUNNON/numbwall10.html That paper also discusses parallel algorithms with time and space complexity of the same order n as the matrix, involving 1-D arrays of finite-state automata. [ Incidentally, the proof given there is analytical, rather lengthy and delicate. It does at least possess the virtue of presumable correctness. Which is better than can be said for the argument appearing in another earlier publication, by pair of gentlemen mustering ingenuity sufficient to recycle the preprint and claim attribution, but evidently remaining in ignorance of its subsequent retraction by the original author --- who, under the circumstances, is maliciously content to remain anonymous. The result has since been buttressed by an elegant and more general algebraic argument, which (typically) remains unpublished. ] Fred Lunnon
For circulants := diag(vec(v)) we certainly have det = prod of elements of Fourier transformed vec(v)
The following should be useful: Victor Y. Pan: Structured matrices and polynomials: Unified Superfast Algorithms, Springer-Verlag, (2001)
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun