0
$\begingroup$

I am parsing a large ASCII sparse matrix, output of PETSc, but my current implementation is impossibly slow. I don't know how I could speed that up.

The ASCII file of a sparse PETSc aij matrix is as follows (with col being an integer index, and val being a floating point, e.g., 1.372e-1):

row0: (col, val) (col, val) ...
row1: (col, val) (col, val) ...
row2: (col, val) (col, val) ...
...

What I did right now is simple: with a text editor I remove the rowX: part and then use the following code:

(* Open and split into lines *)
Ktxt = StringSplit[Import["K.txt"], "\n"]

(* convert ASCII exponents *)
convert[s_] := ToExpression /@ StringReplace[StringSplit@s, "e" | "E" :> "*^"]

l = {}

(* For each row, convert and append element *)
For[r = 1, r <= Length[Ktxt], r++,
 t = StringSplit[Ktxt[[r]]];
 For[i = 1, i <= Length[t], i += 2,
  s1 = (convert[StringReplace[t[[i]], {"(" -> "", "," -> ""}]])[[1]];
  s2 = (convert[StringReplace[t[[i + 1]], ")" -> ""]])[[1]];
  AppendTo[l, {r, s1 + 1} -> s2]
  ];
 If[Mod[r, 100] == 0, Print["row ", r]]
 ]

(* Make the sparse matrix *)
MM = SparseArray[l]

Is there a way to make this faster? For a 15,000 x 15,000 matrix with 800,000 non-zero elements it takes hours.

Thank you!

$\endgroup$
  • 1
    $\begingroup$ Why not have PETSc save your matrix to a format that Mathematica can Import[], like *.mtx? $\endgroup$ – J. M. will be back soon May 29 '17 at 12:26
  • $\begingroup$ First, I am not skilled in PETSc, which is one package used by another software I am using, and second, my goal is to improve my Mathematica knowledge. $\endgroup$ – senseiwa May 29 '17 at 12:43
  • $\begingroup$ Please provide a sample aij matrix file (or code that generates its content) -- it is much more likely to get responses to your question. $\endgroup$ – Anton Antonov May 29 '17 at 13:06
  • $\begingroup$ I modified the question: that sample code is the file itself, actually. $\endgroup$ – senseiwa May 29 '17 at 13:16
  • $\begingroup$ cant test here, but what does Import[..,"Table"] do with that? $\endgroup$ – george2079 May 29 '17 at 13:42
1
$\begingroup$

You are doing string operations on a much finer granularity level than necessary. The code below is fairly fast on my computer for matrices with the size and fill-in you mention.

Data generation

Since no data was provided in the question let us generate such data.

smat = AdjacencyMatrix[RandomGraph[{15000, 400000}]]

Dimensions[smat]    
(* {15000, 15000} *)

smat["Density"]*Apply[Times, Dimensions[smat]]    
(* 800000. *)


exportRows = 
  Map[{#[[1, 1, 1]], 
     Transpose[{#[[All, 1, 2]], RandomReal[{0, 10}, Length[#]]}]} &, 
   GatherBy[Most[ArrayRules[smat]], #[[1, 1]] &]];

aijText = 
  StringJoin@
   Riffle[Map[
     ToString[#[[1]]] <> ":" <> 
       StringReplace[
        StringTake[ToString[#[[2]]], {2, -2}], {"{" -> "(", 
         "}" -> ")", "," ->" " }] &, exportRows], "\n"];

 StringLength[aijText]

 (* 13872182 *)

Conversion

Here is the conversion code. Note the use of Cases to eliminate wrong parsings. (I was too lazy to identify the reason, for smaller matrices the process happens without problems...)

AbsoluteTiming[
 t1 = StringReplace[
  aijText, {")" ~~ (WhitespaceCharacter ..) ~~ "(" -> "},{", 
  "(" -> "{", ")" -> "}", 
   x : NumberString ~~ (WhitespaceCharacter ..) ~~ y : NumberString :> x <> "," <> y}];
]

(* {1.534615, Null} *)

AbsoluteTiming[
 triplets = Flatten[#, 1] &@
    Map[Flatten /@ Thread[#] &,
     Map[{ToExpression[#[[1]]], 
        ToExpression["{" <> #[[2]] <> "}"]} &,
      Map[StringCases[#, x__ ~~ ":" ~~ y__ :> {x, y}][[1]] &, 
       StringSplit[t1, "\n"]]]];
 ]

(* {2.763, Null} *)

triplets // Length
(* 799893 *)

AbsoluteTiming[
 triplets = Cases[triplets, {_?NumberQ, _?NumberQ, _?NumberQ}];
 ]

(* {0.520321, Null} *)

triplets // Length    
(* 799893 *)

smat2 = 
 SparseArray[Thread[#[[All, 1 ;; 2]] -> #[[All, 3]]] &@triplets]
$\endgroup$
  • $\begingroup$ The example in the question doesn't imply , between adjacent ) and (. Hence I would replace StringReplace[aijText, {"(" -> "{", ")" -> "}"}] with StringReplace[aijText, {") (" -> "},{", "(" -> "{", ")" -> "}"}] (assuming one space between adjacent ) and (). $\endgroup$ – Alexey Popkov May 29 '17 at 14:17
  • $\begingroup$ @AlexeyPopkov Thank you, for looking into this, I made the related corrections. $\endgroup$ – Anton Antonov May 29 '17 at 19:37
  • $\begingroup$ @AntonAntonov I just had to add triplets = Map[{#[[1]] + 1, #[[2]] + 1, #[[3]]} &, triplets] to make this work, as the original file starts with zero, and Mathematica complains with SparseArray::posr: The left-hand side of {0,0}->1 in {{0,0}->1,{0,2}->2,{1,1}->1,{2,0}->-(1/1000),{2,2}->2} is not a position or a pattern that will match the position of an element in an array with depth 2.. Thanks! $\endgroup$ – senseiwa May 30 '17 at 10:15
  • $\begingroup$ @senseiwa Ok, I am glad my answer was useful. $\endgroup$ – Anton Antonov May 30 '17 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.