| Re: [eigen] Complexity of setFromTriplets |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Complexity of setFromTriplets
- From: Nathan Yonkee <nathan.yonkee@xxxxxxxxx>
- Date: Thu, 8 Oct 2015 14:20:14 -0600
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:subject:message-id:in-reply-to:references:mime-version :content-type:content-transfer-encoding; bh=AqwoFSmOFfvm370g3LS1eJLjGC/T2Gqxuo1TxsF36UQ=; b=lSxt7ZZyzfXltns8bmX61gB9v94fkQvYibQ5rsXXEhPC2IwaqVrJPWKTw6JN17J2K5 5fLMs3Vjo5iKxtFjg4bSRvH9aBh31MBzZXkh8UYCylnQYIEQycjsW3xyL62L+1b8mKb3 LoWZwcJ9ESBtO690dmlAvqK0s7RU80sEvxDnO9rtj8apTjbl1uoFw5nBKG/HTkUqo4gQ wjQs7qUh0nSu0KrTDgrFV6qfu+qQo6Po8mt2ncA7ZpZiYy2J+HxGgrPpYNYrZcHx7JiN MZ8FQbg26G10MBvSpgIrriSYef6ml2C7phjy741NiM0c3OmXfyJWzI6LQx1TeBFK3FjL 6cTg==
Cory,
Simply setting the values is independent of the matrix size. If I set only the first element, that's only one set of operations, nothing is done on the rows or columns. Additionally, a matrix is sparse when n = O(r) with r being the longer dimension, so O(n) + O(r) + O(c) is still O(n). So for an algorithm like multigrid applied to a sparse matrix, the complexity is based on size (I think), but is still O(n) because every dimension is no greater than O(n).
On Thu, 08 Oct 2015 12:39:56 +0200
coryaden@xxxxxxxxxx wrote:
> Hello,
>
> in the documentation of the class Eigen::SparseMatrix< _Scalar,
> _Options, _Index > it is claimed that the function setFromTriplets was a
> "O(n) operation, with n the number of triplet elements".
> O(n) suggests that the matrix dimensions do not effect execution time,
> which is wrong. It should be O(n+r+c), with n number of triplets and r,c
> the number of rows and columns of the SparseMatrix<>.
>
> Cory Aden
>
>
--
Nathan Yonkee <nathan.yonkee@xxxxxxxxx>