polyvalm2 - A faster matrix polynomial evaluator

版本 1.1.0.0 (4.5 KB) 作者: James Tursa
polyvalm2 evaluates a polynomial with a matrix argument faster than the MATLAB function polyvalm.
685.0 次下载
更新时间 2009/11/11

查看许可证

polyvalm2 evaluates a polynomial with a square matrix argument faster than the MATLAB built-in functions polyvalm or mpower.

Y = polyvalm2(P,X), when P is a vector of length N+1 whose elements are the coefficients of a polynomial, is the value of the polynomial evaluated with matrix argument X. X must be a square matrix.

Y = P(1)*X^N + P(2)*X^(N-1) + ... + P(N)*X + P(N+1)*I

Class support for inputs P, X:
float: double, single

The polyvalm2 speed improvements come from the following:

1) The MATLAB built-in function polyvalm uses Horner's method. polyvalm2 uses a binary decomposition of the matrix powers to do the calculation more efficiently, reducing the total number of matrix multiplies used to calculate the answer.

2) polyvalm calculates the product of a scalar times a matrix as the product of diag(scalar*ones(etc))*matrix ... i.e. it does a matrix multiply. polyvalm2 will calculate this more efficiently as the simple product scalar*matrix.

3) polyvalm does all of the calculations shown above, even if the coefficient P(i) is zero. polyvalm2 does not do calculations for P(i) coefficients that are zero.

4) polyvalm converts sparse matrix inputs into full matrices to do the calculations, whereas polyvalm2 keeps the intermediate calculations and the answer sparse.

The trade-off is that polyvalm2 uses more memory for intermediate variables than polyvalm, so for very large matrices polyvalm2 can run out of memory. In these cases polyvalm2 will abandon the efficient calculation method and just call the built-in polyvalm. For sparse matrix inputs, however, polyvalm2 will typically be more memory efficient than the MATLAB polyvalm function.

Caution: Since polyvalm2 uses different calculations to form the matrix powers, the end result may not match polyvalm exactly. Also, for the case where only the leading coefficient is non-zero, polyvalm2 may not match mpower exactly. But the answer will be just as accurate. And if there are inf's or NaN's involved, then the end result will not, in general, match polyvalm or mpower results. This should not be a great drawback to using polyvalm2, however, since even the MATLAB built-in functions polyvalm and mpower will not match each other in these cases. (By reordering the calculations, the NaN's propagate differently)

引用格式

James Tursa (2024). polyvalm2 - A faster matrix polynomial evaluator (https://www.mathworks.com/matlabcentral/fileexchange/25780-polyvalm2-a-faster-matrix-polynomial-evaluator), MATLAB Central File Exchange. 检索时间: .

MATLAB 版本兼容性
创建方式 R2007a
兼容任何版本
平台兼容性
Windows macOS Linux
类别
Help CenterMATLAB Answers 中查找有关 Polynomials 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
版本 已发布 发行说明
1.1.0.0

Modified the code so that if an input matrix is sparse, the intermediate calculations and final answer will also be sparse. Note that this is different behavior from the MATLAB intrinsic polyvalm.

1.0.0.0