Fast Solutions of Exact Sparse Linear Equations 

In[1]:=

X (*Sparse invertible integer matrix model, with density \ \[GreaterEqual] 2/d*) randomSparseIntegerMatrix[d_] := Block[{m = 500}, SparseArray[ Table[Rule[{RandomInteger[{1, d}], RandomInteger[{1, d}]}, RandomInteger[m]], {2 d}], {d, d}] + m*IdentityMatrix[d] ]

In[2]:=

X m9s = {0.09381, 0.1328, 0.3937, 0.7137, 1.529, 1.073, 1.492}; m8s = {0.2194, 0.5408, 1.060, 1.882, 3.480, 5.145, 7.248}; mpl16s = {4.658, 15.08, 42.23, 90.97, 177.5, 329.2, 487.8};

In[3]:=

X (*Permuted block triangular matrix model,of dimension 5n*) randomBlockSparseIntegerMatrix[n_] := Block[{blockSize = 5, d, l, dims, rdims, cdims, mat}, d = ConstantArray[blockSize, n]; l = Table[ RandomInteger[{1, 5}, {d[[i]], d[[j]]}], {i, Length[d]}, {j, i}]; dims = Map[Dimensions, l, {2}]; rdims = Map[First, dims, {2}]; cdims = Map[Last, dims, {2}]; rdims = Map[First, rdims]; cdims = Last[cdims]; mat = ArrayFlatten[ Table[ If[j <= i, l[[i, j]], ConstantArray[0, {rdims[[i]], cdims[[j]]}]], {i, Length[rdims]}, {j, Length[cdims]}] ]; mat[[RandomSample[Range[n*blockSize]], RandomSample[Range[n*blockSize]]]] ]

In[4]:=

X m9s = {0.01985, 0.04545, 0.1167, 0.1880, 0.4029, 0.6537, 1.293}; m8s = {0.01325, 0.03172, 0.4780, 0.5078, 0.8436, 1.974, 2.437}; mpl16s = {1.015, 7.228, 36.87, 148.9, 534.6, 1442., 3829.};

Shown are timings for solving systems of linear equations represented by sparse square integer matrices. The experiment was performed on an Intel Xeon 3.07 GHz 64-bit Linux system, with a time limit of 4200 seconds. The number at the bottom tells how many times faster Mathematica 9 is than Maple 16.

Shown are timings for solving systems of linear equations represented by square integer matrices with a permuted triangular block structure.