flop count for ?gesvd

Open discussion for MAGMA

flop count for ?gesvd

Postby bravegag » Fri Aug 09, 2013 8:28 am

Hello,

I was looking for the actual flop count corresponding to ?gesvd but could not find it in the usual places. I also noticed it is not provided in e.g. testings_dgesvd.

I assume the flop count for ?gesvd would be worst case and according to the Golub book and when computing U and V about:
14mn^2 + 8n^3

Would this assumption be acceptable?

TIA,
Best regards,
Giovanni

PS: book link

http://books.google.ch/books?id=mlOa7wP ... op&f=false
bravegag
 
Posts: 23
Joined: Wed Jun 19, 2013 9:51 am

Re: flop count for ?gesvd

Postby mgates3 » Fri Aug 09, 2013 11:59 am

The SVD is necessarily an iterative process, therefore no exact flop formula is possible. It also depends on which singular vectors are required. Some approximations given in Matrix Computations, 3rd ed., Golub & Van Loan, page 254 are

- singular values only, 4mn^2 - 4n^3/3
- singular values and some singular vectors U (m x n) and V (n x n), 14mn^2 + 8n^3

An exact flop count would require instrumenting the code, e.g., with PAPI.
-mark
mgates3
 
Posts: 442
Joined: Fri Jan 06, 2012 2:13 pm

Re: flop count for ?gesvd

Postby bravegag » Fri Aug 09, 2013 12:22 pm

Thank you! Instrumenting with PAPI would be an overkill for the moment so I think I will stick to the approximate (kind of ceil) flop count that you mention.

btw This is the the relevant code in the benchmark project:
https://github.com/bravegag/eigen-magma ... in.cc#l135

Best regards,
Giovanni
bravegag
 
Posts: 23
Joined: Wed Jun 19, 2013 9:51 am


Return to User discussion

Who is online

Users browsing this forum: Bing [Bot] and 4 guests

cron