# Storage strategy for polynomials

What is the most space efficient way to store arbitrary length univariate polynomials? I have a large amount of polynomials that look like

``````3*x^7  + 12*x - 13
9*x^32 - x^14 + 2*x^3 - 9
...
``````

Each polynomial is composed of an arbitrary number of integer coefficients for a given power, e.g. the following polynomials could be stored as

``````(3,7) (12,1) (-13,0)
(9,32) (1,14) (2,3) (-9, 0)
``````

which is in fact exactly what I do now. I have a SQLite schema that looks something like

`````` CREATE TABLE poly_lookup (
poly_id INTEGER PRIMARY KEY AUTOINCREMENT
);
CREATE TABLE poly (
poly_id INTEGER,
coeff   INTEGER,
power   INTEGER
);
CREATE INDEX idx_poly  ON poly(poly_id);
``````

This works, but I'm not sure this is the most space efficient solution. caveat responsum, I only know SQLite, but I would be willing to learn a completely new type of database system (mongodb, neo4j, ...) if it would help the solution.

• Your solution seems legit. I would add a NOT NULL constraint to poly.poly_id column to ensure each row in poly is associated with a polynomial, but otherwise it's a reasonable RBDMS solution to the problem. If you only care about space and nothing else, you could denormalize your schema and put polynomial coefficients and powers into a string field in the poly_lookup table (serizalized, i.e. 3,7,12,1,-13,0 for your first poly) but that would take all the flexibility out of the solution. May 28 '15 at 20:48
• @zgguy Wouldn't storing them as strings be inefficient? They are integers, so I feel like there should be a more optimal way of storing them. May 28 '15 at 20:57
• Well, yes, integers should be stored as integers. I definitively think your current solution is much better than storing numbers as strings, I merely suggested it as something to try if you really want to. It is true that a single integer will usually take less place on disk than "serialized" as varchar, however, you have 3 integers per row in your table + you have an index, which can take up a significant amount of space. Bottom line - you can't be sure until you try. But, again, your current solution is probably the way to go, not because of storage, but because of flexibility. May 28 '15 at 21:55