The following should be state of the art efficient when a) the entry field, F, is a finite field or the rational numbers. and b) the n by n matrix is sparse or structured such that the matrix-vector product costs substantially less than n^2 entry field operations.

Functionality to be provided:

1. Minimal polynomial
   1. of A, i.e. of a matrix,
   2. of A,b, i.e. of a vector sequence,
   3. of u,A,b, i.e. of a sequence in the entry field.
2. Rank of a matrix.
   1. Probabilistic
   2. Deterministic in characteristic 0
3. Determinant.
   • quick determination of det(A) == 0, of det(A) != 0.
4. Trace.
5. Solve linear system Ax = b.
   1. Non-singular
   2. Singular
      1. random solution
      2. certificate of inconsistency
      3. Null space basis
   3. Methods... Wiedemann, Lanczos, Conjugate Gradient, blocks

Further functionality:

• All of the above when A is a submatrix of B.
• Characteristic polynomial
• Invariant factors
• Frobenius form, Rational Jordan form (and/or primary canonical form)
• Similarity, Equivalence testing.
• Eigenvalues/Eigenvectors...
• All of the above for special cases ( symmetric ... )

• Integer invariant factors (Smith form)
• Is there no Hermite form, Popov form for sparse case?
• Diophantine system solution
• Matrices over a comm. ring.