0 people like it.

Density of sparse matrix product

A quick exploration of the rather useless question "how does the density of the product of 2 sparse matrices look like?"

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
// Completely useless exploration of the question:
// how sparse is the product of 2 sparse matrices?

#r "FSharp.PowerPack.dll"

let density (M: Matrix<float>) =
    let elements = M.NumRows * M.NumCols |> (float)
    let nonZero =
        M
        |> Matrix.map (fun e -> 
            if e = 0.0 then 0.0 else 1.0)
        |> Matrix.sum
    nonZero / elements
  
let dense = matrix [ [ 42.0; 0.0  ]; 
                     [-1.0;  123.0] ]
let sparse = matrix [ [ 0.0; 1.0 ]; 
                      [ 0.0; 0.0 ] ]

printfn "Dense matrix: %f" (density dense)
printfn "Sparse matrix: %f" (density sparse)

let rng = new System.Random()

let create n density =
    Matrix.create n n 0.0
    |> Matrix.map (fun e -> 
        if rng.NextDouble() > density 
        then 0.0 
        else 1.0)

// Run r times the product of 2 matrices
// of density d, and size n, and compute
// the average density
let simulation n d r =
    Seq.initInfinite (fun index ->
        let m1 = create n d
        let m2 = create n d
        density (m1 * m2))
    |> Seq.take r
    |> Seq.average

// Relationship between density and density
for density in 0.0 .. 0.05 .. 0.5 do
    simulation 10 density 1000
    |> printfn "Density %f -> Result is %f" density

// Relationship between size and density
for size in 5 .. 5 .. 50 do
    simulation size 0.1 1000
    |> printfn "Size %i -> Result is %f" size
val density : M:'a -> float

Full name: Script.density
val M : 'a
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val elements : float
val nonZero : float
val dense : obj

Full name: Script.dense
val sparse : obj

Full name: Script.sparse
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val rng : System.Random

Full name: Script.rng
namespace System
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
System.Random() : unit
System.Random(Seed: int) : unit
val create : n:'a -> density:'b -> 'c

Full name: Script.create
val n : 'a
val density : 'b
System.Random.NextDouble() : float
val simulation : n:'a -> d:'b -> r:int -> float

Full name: Script.simulation
val d : 'b
val r : int
module Seq

from Microsoft.FSharp.Collections
val initInfinite : initializer:(int -> 'T) -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.initInfinite
val index : int
val m1 : int
val m2 : int
val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val average : source:seq<'T> -> 'T (requires member ( + ) and member DivideByInt and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.average
val density : float
val size : int
Raw view Test code New version

More information

Link:http://fssnip.net/eS
Posted:11 years ago
Author:Mathias Brandewinder
Tags: math , algebra , simulation