Atlas home || Conferences | Abstracts | about Atlas

2nd Croatian Mathematical Congress
June 15-17, 2000
Croatian Mathematical Society and Dept. of Math., Univ. of Zagreb
Zagreb, Croatia

Organizers
Hrvoje Sikic (president), Pavle Pandzic (secretary)

View Abstracts
Conference Homepage

Accelerating bidiagonal divide and conquer by fast multipole method
by
Ivana Hunjet
Departement of Mathematics, University of Zagreb

Bidiagonal matrices arise when one computes the singular value decomposition (SVD) of a general matrix by first reducing it to a bidiagonal form. Currently, the fastest method for computing all singular values and singular vectors of a bidiagonal matrix larger than n=25 is divide-and-conquer algorithm (BDC). BDC computes all singular values in O(n2) flops and all singular vectors in O(n3) flops. Using fast multipole method (FMM), invented by Carrier, Greengard and Rokhlin for the problem of computing mutual forces on n electrically charged particles, BDC can be accelerated to compute all the singular values in O(n log2 n log22 \epsilon) and all the singular values and vectors in O(n2 log22 \epsilon) flops.

Date received: March 15, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caex-13.