What's the computational complexity of A\b in MATLAB? (A is a sparse non-square matrix)

5 次查看（过去 30 天）

JUNWEI ZHANG 2017-8-7

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/351897-what-s-the-computational-complexity-of-a-b-in-matlab-a-is-a-sparse-non-square-matrix

评论： John BG 2017-8-8

MATLAB document says that if A is sparse and not a square, \ operation will turn to QR solver. I'm not very familiar with QR factorization either. Can anybody give an approximation of the complexity?

Thanks,

Junwei

2 个评论
显示无隐藏无

Walter Roberson 2017-8-7

http://epubs.siam.org/doi/abs/10.1137/0909057

However, that theory might not match the implementation.

John BG 2017-8-8

It's time.

Computation complexity is the time it takes to solve it, that is usually equivalent to the amount of required computations, provided the time per operation is constant and known.

As explained in the link supplied by Walter, one can find bounds to the amount of operations

.. O(n^{{3 / 2}} )$ arithmetic operations, and the number of nonzeros in the Cholesky factor is $O(n\log n)$.

.. complexity bounds can be attained when A is nonsymmetric and indefinite, and either Gaussian elimination with partial pivoting or orthogonal factorization is applied.

.. Numerical experiments for a sequence of irregular mesh problems are provided.

So, consider tic tocing the operations of the experiments you perform, and then correlating the results to the amount of nonzeros, amount of operations, and then you will have measured the computational complexity of QR factorisation.

请先登录，再进行评论。

请先登录，再回答此问题。