I should make it clear that Conway & Guy did indeed acknowledge me in their book. The meticulous if unimaginative adopters of my early draft of a dud proof (one of a monotonously increasing sequence of similar lemons) were by contrast francophones, whose identities deserve no further publicity. On 3/10/14, Warren D Smith <warren.wds@gmail.com> wrote:
... --that paper is rather immensely long and annoying to read,...
Not half as long and annoying as it was to write! For some reason, this subject is replete with results which appear straightforward to establish, while their eventual proofs prove otherwise. A related example is Berlekamp's algorithm, of which I have yet to encounter a demonstration I feel confident that I fully understand.
but I suspect some of this "number wall" stuff must be equivalent to Carroll condensation applied to Toeplitz matrices, i.e. the latter was already known under other names. Incidentally there are still more names such as "lozenge algorithms" out there.
The elementary "number wall" recurrence goes back at least to Jacobi; I first encountered it in the form of Rutishauser's "QD" algorithm for matrix eigenvalues. The nontrivial challenge comes along when that demands division by zero, which must somehow be circumvented ... Fred Lunnon On 3/10/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
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