Implementing SparseArrays

[rocky]

From #1692 (comment)

A note on SparseArray:

...

Back in 2024, I underestimated the complexity of enhancing SparseArray, and honestly, my research workload became quite heavy, so I had to put open-source contributions on hold.

However, as part of my research, I’ve been working on a C++ based sparse tensor project SparseRREF during this time. Through this, I’ve gained more experience in implementing sparse tensor calculations. I remember @rocky once mentioned that "we are not experts in how to implement sparse arrays." While I'm not an expert yet, I definitely feel more confident about implementing sparse arrays now!

Recent work by @bdlucas1 on better-performing plotting has revealed a few things.

First, the datatype wrapping we do on individual numbers can kill performance, especially for array-like things. To address this, NumericArray was introduced at the atom level. (We do not have the user-facing built-in function implemented right now, which would allow for more pervasive user-directed use.) And if we were to add the user-facing function, we would also need to incorporate that kind of object into other built-in functions.

Second and related: using NumPy's array implementation is a big win. Therefore, SparseArray might be implemented similar to NumericArray. If that is the way we decide to go, it would be another kind of atom in mathics.core.atoms.arrays.

Third and related: Conversion into and out of wrapped-numeric-type Mathics3 lists is killing performance as well. So to reduce this, if we can catch and convert computations at a high-enough level before (wrapped) data is generated, that too is a big win. Plotting is a special case where we can do this. But to do this, you need a "compiler" which will do the translation. @bdlucas1 has a compiler for the special case of pure functions. These get translated into SymPy expressions involving NumPy arrays using SymPy's lambdify.