I am dealing with large, sparse, rational matrices that I need to determine the nullspace of. Currently, I have one that is about 12000x12000 (but not square), where one in every 2000ish elements is nonzero. Subsequent matrices will grow both in size and sparsity.
Most nullspace algorithms rely on bringing the matrix in (some form of) a reduced row-Echelon form, and then reading the nullspace vectors off of that form. Since these algorithms require large amounts of elementary row operations, I would think that using Compressed Row Storage is the best option, since it allows easy acces to full rows, which is what is needed for the row operations.
However, as a part of these operations, it is required to insert elements in the sparse matrix occasionally. Now, as I understand it, inserting elements in a CRS matrix becomes increasingly expensive when the size of the matrix grows. Are there other options for the storage or the nullspace algorithm that avoids this problem?