Simple operations with symbolic variables

Question

Ben Radu 2017-2-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/326389-simple-operations-with-symbolic-variables

评论： Walter Roberson 2017-3-2

Hello everybody,

I'm new to Matlab. I would like to ask if anyone knows what's the time complexity of the addition / subtraction operations with symbolic variables.

Example:

syms a b
A = a^2*b^2+a^3*b^3
B = a^2*b^2+a*b

I would like to know what's the time complexity of this simple operation:

A - B = a^3*b^3 - a*b

I'm not sure about how Matlab calculates it.

(note that each variable has no given value).

Thank you!

5 个评论
显示 3更早的评论隐藏 3更早的评论

Karan Gill 2017-3-2

Ah then use tic and toc as John said.

Walter Roberson 2017-3-2

在 MATLAB Online 中打开

Unfortunately using tic and toc to measure algorithm complexity is tricky.

For example, the algorithm complexity of

for k =1:n
  H(k) = 1;
end

is O(n). But if you code that and test with tic toc, you will find that the time is O(n^2) or worse, because of the way that MATLAB handles expanding arrays (notice that I did not preallocate, which is a matter irrelevant to algorithm complexity)

请先登录，再进行评论。

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

Answer 1

Walter Roberson 2017-2-22

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/326389-simple-operations-with-symbolic-variables#answer_255917

The time complexity of symbolic operations is unspecified, undocumented, and subject to change between versions.

Time complexity of addition and multiplication is usually talked about abstractly as if addition of any two numbers takes the same time independently of the values of the numbers, and if multiplication of any two numbers takes the same time independently of the values of the numbers -- and time complexity calculations equate the two times, as if the time to add two numbers is the same as the time to multiply two numbers. For the purposes of what "time complexity" computes, it is irrelevant that the time to do an addition is not the same as the time to do a multiplication as long as the time for the multiplication is a constant multiple of the time to do addition. 18 cycles (for example) instead of 3 cycles (for example) is not important as long as the implementation is some constant multiple 18/3 or 68/9 or whatever it happens to be for the implementation.

However, implementations of symbolic values need to deal with the fact that values are not constant length -- the space required to represent the number 3 might be different than the space required to represent 33 (as would be the case for binary coded decimal, BCD), or the space required to represent 333 (which exceeds the value representable in an 8 bit byte.) Because of this factor, the time required for additions or multiplications are not constant but instead depend upon value.

For addition of two groups of blocks of values such that each block represents an integer (e.g. , if you broke an integer up into bytes, then you each integer would be represented by a group of bytes and you would have two such groups to add two numbers), the traditional "long form" method is to add the lowest two corresponding blocks, detect carry, add the next two corresponding blocks together with the carry from the first set, detect carry from that, add the next two corresponding blocks together with the carry, and so on. This requires time proportional to the number of blocks in a group.

But consider that if there were no carries that if you had the hardware resources you could add each pair of corresponding blocks simultaneously. Then you have to do fix-up for the carries, and the fix-up might trigger a carry, and so on. Can this approach save you anything in the long run? It turns out that there are algorithms that can add in parallel and propagate carry faster than linearly. And that starts to matter if you just happen to be using a processor that has SIMD (Single Instruction, Multiple Data) class of instructions that can accelerate performance. Therefore, the time complexity of addition of variable-length values depends upon the size of the values and upon the available instruction set and upon the quality of implementation.

Worst case for addition of variable length objects is that the time taken is proportional to log() of the the larger value.

Extended precision multiplication is more complicated. Going back in my memory several decades, I seem to recall that worst case would be proportional to the product of the logs of the two values, but I could be wrong. I suggest you examine John D'Errico's Variable Precision Integer (VPI) File Exchange Contribution.

All of this leads to situations where the Time Complexity of a symbolic algorithm can potentially be improved by techniques such as re-centering, to reduce the values used so that the extended precision operations take less time, even though that might appear to increase the operation count, because the assumption that multiplication takes a constant factor more time than addition is no longer valid.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Walter Roberson 2017-2-22

The algorithms for parallel sorts baffle me; understanding time complexity of multi-threading can be tough.

I have not seen any clear evidence that the MuPAD kernel uses parallel processing for ordinary operations. Possibly in some of the library functions like numeric ODE.

Ben Radu 2017-2-24

Thank you very much, Walter Roberson, for your very helpful and detailed answer.

请先登录，再进行评论。

Answer 2

Vandana Rajan 2017-2-22

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/326389-simple-operations-with-symbolic-variables#answer_255889

Hi,

To understand how much time a particular MATLAB code takes to execute, you can use the 'tic' and 'toc' functions.

https://in.mathworks.com/help/matlab/ref/tic.html

You may also go for MATLAB profiler to track execution time.

https://in.mathworks.com/help/matlab/ref/profile.html

6 个评论
显示 4更早的评论隐藏 4更早的评论

Walter Roberson 2017-2-22

编辑：Walter Roberson 2017-2-23

在 MATLAB Online 中打开

The sizes are not irrelevant for symbolic work, when it comes to constants, as I explore in my Answer.

Also, when expressions are being added, there is also the need to find corresponding parts to add:

x + 2 + y
5*y + sin(x) + 9

it has to do matching to figure out to add the y and 5*y and the 2 and the 9. But how expensive is that? Well, first you have to ask whether x + 2 is represented the same was as 2 + x and whether the representation is always the same for those expressions. In some symbolic packages, whether x + 2 and 2 + x are both transformed to x + 2 or both to 2 + x depends on which version was seen first in the session. In the Symbolic Toolbox, there are rules about constant motion and ordering of terms that reduce the cost during processing, but the rules are undocumented and can be tricky to figure out (I explored the behavior of the order of terms in reciprocal of polynomials a couple of months ago; it was obviously consistent internally but what the rule was was far from clear.)

Ben Radu 2017-2-24

编辑：Ben Radu 2017-2-24

Dear Walter Roberson,

Thank you very much for your answer and your comment. Your help was very important.

About (...) " but the rules are undocumented and can be tricky to figure out" (...), I think those rules should totally be documented. Do you maybe know someone I could contact for further information?

Thanks a lot.

Walter Roberson 2017-2-24

Documentation of the internal rules would not necessarily help much. I mentioned above a symbolic math package in which the ordering depends upon which version was seen first in the session: that package explicitly documents that fact and explicitly documents that given two equivalent expressions, the one that is chosen is the one that has the lower address (pointer). As the user has no control over the address something is placed at, this mostly acts to document that you cannot fight the system and cannot rely on the order of terms because it could change any time. It is good to know explicitly that taking shortcuts will probably fail, as it keeps you from wasting time trying to reverse-engineer rules, but really the same thing can be accomplished by just saying "These are internal matters, don't count on them" without documenting what happens in any given release.

请先登录，再进行评论。

Simple operations with symbolic variables

5 个评论
显示 3更早的评论隐藏 3更早的评论

采纳的回答

3 个评论
显示 1更早的评论隐藏 1更早的评论

更多回答（1 个）

6 个评论
显示 4更早的评论隐藏 4更早的评论

另请参阅

类别

标签

Community Treasure Hunt

Simple operations with symbolic variables

5 个评论 显示 3更早的评论隐藏 3更早的评论

采纳的回答

3 个评论 显示 1更早的评论隐藏 1更早的评论

更多回答（1 个）

6 个评论 显示 4更早的评论隐藏 4更早的评论

另请参阅

类别

标签

Community Treasure Hunt

5 个评论
显示 3更早的评论隐藏 3更早的评论

3 个评论
显示 1更早的评论隐藏 1更早的评论

6 个评论
显示 4更早的评论隐藏 4更早的评论