Bug? Strange behaviour of FullSimplify when checking an equality of SparseArray's

Edit (15 Dec '16): bug noticed in v11.0 and reported as CASE:3796403.

Edit (03 May '17): bug fixed in v11.1 (verified in v11.1.1).

I stumbled upon the following strange behaviour. Disclaimer: I present the simplest instance that I could find in which some behaviour occurs that I first noticed in a different, more complicated setting. In particular I understand that there's no reason to work with $1\times1$ sparse arrays with a nonzero entry in general; I am just trying to give a minimal example.

Let's take an algebraic identity that Mathematica doesn't immediately recognize, yet does upon using FullSimplify:

Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2 == 8
FullSimplify @ %

(* Out: *)
Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2 == 8
True


Now consider a "sparse-arrayed version" of the same equation:

SparseArray[{1} -> Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2] == SparseArray[{1} -> 8]

(* Out is of the form *)
SparseArray[< 1 >, {1}] == SparseArray[< 1 >, {1}]


The output is as expected. However, again applying FullSimplify this time returns

SparseArray[{1} -> Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2] == SparseArray[{1} -> 8] ;
FullSimplify @ %

(* Out is of the form *)
SparseArray[< 1 >, {1}] == 0


That seems strange: FullSimplifying an equality of sparse arrays apparently may yield an equality between a SparseArray and a number!

My question is: is this a bug, or can we somehow understand it?

Here are some things that I am not asking. Firstly, the single specified entry of the sparse array is {1}->0: there is no 'mathematical' inconsistency. Secondly, the strange behaviour may be easily avoided: for example, Mathematica does return True when applying FullSimplify to both sides of the equality separately (FullSimplify /@ %) or by first going back to lists (FullSimplify @ Normal @ %).

NB. I'm not sure if it's relevant that Simplify does not yield True for the identity that we started with. For example, the equality a Csc[Pi/5]^2 + a Csc[2 Pi/5]^2 == 4 a (with the a) is not automatically recognized to hold true, but here it suffices to use Simplify; this time applying Simplify to the 'sparse-arrayed version' of that identity just returns True.

Edit (1 dec '16). Above I suggested two workarounds. In general I'd expect the second one (simplifying both sides of the equation separately: FullSimplify /@ %) to be faster but less powerful than the former (first going to normal form: FullSimplify @ Normal @ %). Indeed, on the one hand not going to normal form should save time (especially for large arrays that are fairly sparse). On the other hand, however, the separate simplifications of the two sides of the equation need not yield results written in identical ways, while the simplification of something that actually vanishes should be more likely to yield identically zero.

My additional question is: what would be the fastest way to check the equality given this apparent bug? (I am assuming that we're in a case where FullSimplify can actually recognize the equality between the two sparse arrays as being true.)

1 Answer

I think the culprit is a transformation of A == B into A - B == 0, which is valid for only scalar-valued expressions. (The issue came up in my investigation of this answer. The form x - True == 0 arose from x == True in code not included there. The code x - True == 0 evaluates correctly if x = True but not if x = False. I think it also illustrates that some algebraic transformations of equalities are really only valid for numeric scalars. Since in many cases, equalities are between numeric expressions, it's not clear whether (1) putting all terms on one side should be prohibited, (2) Mathematica should check which expressions are scalars, which is not so easy since Listable functions Sin[x] could be scalars or lists, or (3) we should learn to deal with the pitfall of A - B == 0.)

Another factor is that an equality x == y will not evaluate to True if x and y do not have identical expression trees and at least one of them has a nonnumeric symbol (e.g. Automatic). This will lead to the transformation mentioned above, to see if the two sides will cancel (I think).

Let's store the sparse arrays in variables for convenience. Note the time it takes for the initial comparison of the two sparse arrays. This turns out to be the major component in this small example. A larger example might be necessary to see how the timing scales with size.

sa1 = SparseArray[{1} -> Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2];
sa2 = SparseArray[{1} -> 8];
saeqn = sa1 == sa2; // RepeatedTiming
(*  {0.0022, Null}  *)


Note the expressions they represent; in particular FullSimplify@sa1 is identical to sa2:

InputForm /@ {sa1, FullSimplify@sa1, sa2}
(*
{SparseArray[Automatic, {1}, 0, {1, {{0, 1}, {{1}}},
{Csc[1/7 Pi]^2 + Sec[1/14 Pi]^2 + Sec[3/14 Pi]^2}}]],
SparseArray[Automatic, {1}, 0, {1, {{0, 1}, {{1}}}, {8}}]],
SparseArray[Automatic, {1}, 0, {1, {{0, 1}, {{1}}}, {8}}]]}
*)


We can mimic the behavior of the OP's SparseArray example with a function that can be combined with itself when subtracted like SparseArray:

ClearAll[F];
F /: F[z__, x_] - F[z__, y_] := F[z, x - y];
F[Automatic, Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2] == F[Automatic, 8] //FullSimplify
(*  F[Automatic, 0] == 0  *)


But that does not happen with a function that does not combine with itself when subtracted, because the two sides are simplified to identical expressions:

G[Automatic, Csc[Pi/7]^2 + Sec[Pi/14]^2 + Sec[3 Pi/14]^2] == G[Automatic, 8] //FullSimplify
(*  True  *)


We can see this is the sort of thing that happens with SparseArray:

InputForm[FullSimplify@sa1 - sa2]
(*  SparseArray[Automatic, {1}, 0, {1, {{0, 1}, {{1}}}, {0}}]  *)

InputForm[FullSimplify@saeqn]
(*  SparseArray[Automatic, {1}, 0, {1, {{0, 1}, {{1}}}, {0}}] == 0  *)


Here is a hand-coded way to check equality of two sparse arrays:

ClearAll[checkeq];
checkeq[sa1_SparseArray == sa2_SparseArray] :=
Dimensions[sa1] === Dimensions@sa2 &&
sa1["NonzeroPositions"] === sa1["NonzeroPositions"] &&
sa1["NonzeroValues"] == sa1["NonzeroValues"] &&
sa1["Background"] == sa2["Background"];
checkeq[e_] := e;


Here are a variety of ways to test equality, including checkeq, ranked by speed on the OP's example. Note the numeric ways only test approximate equality. All the timings are much less than the initial time it took saeqn to return unevaluated. I'm not sure what to extrapolate from the small size of the example as far as timing goes.

saeqn // N[#, 30] & // RepeatedTiming
(*  {1.75*10^-6, True}  *)

saeqn // checkeq // RepeatedTiming
(*  {5.9*10^-6, True}  *)

saeqn // FullSimplify[#,
TransformationFunctions -> {Automatic, checkeq}] & // RepeatedTiming
(*  {0.000011, True}  *)

saeqn // N // RepeatedTiming
(*  {0.0000130, True}  *)

saeqn // FullSimplify[#,   (* this might not work on large, sparse arrays *)
TransformationFunctions -> {Automatic, Normal}] & // RepeatedTiming
(*  {0.000014, True}  *)

FullSimplify@sa1 == sa2 // RepeatedTiming
(*  {0.000015, True}  *)

FullSimplify[sa1 - sa2] == SparseArray[{}, Dimensions@sa1] // RepeatedTiming
(*  {0.000039, True}  *)

• Dear @Michael E2, thank you for your elaborate answer! I would hope a next Mathematica version goes for option (2) that you mention in your first paragraph: that would surely be the most satisfactory. I do agree that the Listable property complicates matters somewhat, but I'd think that can be taken into account. In case you'd be interested to test the timings for larger arrays I can provide for any integer $L$ more complicated examples with arrays of size $2^L \times 2^L$ that I encountered in my research, and were the motivation for my question. Dec 6, 2016 at 15:51
• NB. For the record, the option FullSimplify /@ saeqn that I suggested in my OP has a computation time between the final two that you wrote down. Dec 7, 2016 at 14:41
• Also, just out of curiosity, do you think this qualifies as a bug? Dec 7, 2016 at 21:34
• Yes, SparseArray is clearly an array and not a scalar; therefore, it is clearly an error. You should report it to WRI and they should try to fix it. Note Simplify has some notion of arrays: Compare Simplify[f[x] == f[x] + g[x]] vs. Simplify[f[x] == f[x] + g[x], f[x] \[Element] Arrays[{1}]]. I'm not sure I'd say the first one is a bug, since I rely on that sort of cancellation quite often. Dec 7, 2016 at 21:52
• Am I allowed to add the label "bugs" to this post then? Dec 7, 2016 at 22:30