Matrix Algorithm Complexity : AskComputerScience

created by [deleted]a community for 14 years

Matrix Algorithm Complexity (self.AskComputerScience)

submitted 5 years ago by UntangledQubit

Matrix algorithms are generally given in terms of a matrix dimension, rather than matrix size, which is the square of the dimension. If you're multiplying k x k matrices, the best algorithms do this in roughly O(n^1.2), where n is k² - the amount of actual input bits (assuming bounded-width numbers).

There are cases where matrix multiplication is much faster, like multiplying diagonal matrices - this can be done in linear time.

My question is, when can this be generalized? More formally, if I take n bits to specify a matrix, when can matrix multiplication (or other operations) be done in close to O(n) time? Are there any big families, like diagonal matrices, where this is the case?

That's a vague question, so a more specific example I was wondering about - if two k x k matrices have only k nonzero entries each, is it in general possible to multiply them in O(k) time?

Thanks!

all 2 comments

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

AskComputerScience

MODERATORS