Simple operations with symbolic variables

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!

[John Chilleri]

This may or may not be useful, but you can use tic and toc to measure how long the subtraction takes.

On my computer, it requires about .0012 seconds to complete the operation (really bad computer).

[Karan Gill]

Why do you need this information? Note that symbolic calculations are slower than numeric. Use numeric if you need speed.

Karan (Symbolic doc)

[Ben Radu]

Thanks for your comment,

I need this information to analyze an algorithm which uses simple operations with symbolic variables.

Yes, symbolic calculations are slower than numeric but it would be interesting to know how much slower. Thank you for your help!

[Karan Gill]

Ah then use tic and toc as John said.

[Walter Roberson]

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]

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.

[John D'Errico]

Walter make an important point that the time complexity of an addition is completely dependent on the complexity of the operands. This is different from the same operation on doubles, where it can be fairly consistent. Not completely so, since pipelining, multi-threading, etc., can totally screw around with any big O estimates even for doubles.

[Walter Roberson]

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]

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

Answer 2

[Vandana Rajan]

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

[Ben Radu]

Dear Vandana Rajan,

Thank you very much for the answer, this helped me. However, i was also trying to figure out the complexity of this operation, in terms of "Big O". For example, the behavior of the following operation (simple additions and subtractions)

1+9-6+26 = 30

can be described by O(n).

My question is: how can the behavior of simple symbolic additions and subtractions can be described?

Example:

x^2 + x^5 + x^3*y^2 - x^2 + 2*x^5

= x^3*y^2 + 3*x^5

Is it O(n) again? What does Matlab exactly do to find the result?

Thank you very much for the help!

[John Chilleri]

Hello,

Would you mind clarifying your question:

1+9-6+26 = 30

is O(1) as it does not scale with any n.

I would suspect the above A-B is also O(1) as it will always take the same amount of time, as it is symbolic, and the sizes of A and B are irrelevant.

So what exactly do you mean by run complexity of these things?

Sorry if this was confusing, I just want to make sure we are on the same page!

[Ben Radu]

Dear John Chilleri, Thank you for your comment. Yes, sorry, I was not precise (I also apologize for my english since I'm not native).

With O(n) I was referring to the complexity of summing #n values. For example, given an array a[ ] with n elements, the following code is O(n):

 sum = 0;
 for(i=0; i<n; i++)
 sum = sum + a[n];

If we consider a single operation, yes, it is O(1).

" I would suspect the above A-B is also O(1) as it will always take the same amount of time, as it is symbolic, and the sizes of A and B are irrelevant."

This is exactly what I'm trying to figure out: is the above A-B O(1) and the sizes of A and B irrelevant? This would help me a lot.

Thank you very much.

[Walter Roberson]

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]

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]

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.