Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

No effective way to generate large sums #96

Open
VisualCoder123 opened this issue Oct 12, 2021 · 0 comments
Open

No effective way to generate large sums #96

VisualCoder123 opened this issue Oct 12, 2021 · 0 comments

Comments

@VisualCoder123
Copy link

Hi!

currently I'm trying to generate a large symbolic expression (over 1 000 000 terms). Unfortunately, performance was not very high so I wrote a benchmark to demonstrate the problem.

The idea of a benchmark is to generate a list of n nonlinear terms (so they wouldn't collapse to one term) and then calculate their sum. I used sin(ix)*cos(iy), i=1..n for nonlinear terms and wrote minimal test code:

open MathNet.Symbolics
open Operators

[<EntryPoint>]
let main argv =
    let x = symbol "x"
    let y = symbol "y"

    let terms n= seq {for i in 1..n -> sin(i*x)*cos(i*y)}

    let sw = new System.Diagnostics.Stopwatch()

    sw.Start()
    let res = terms 10_000 |> Seq.toList |> sum
    sw.Stop()

    printfn "Time %f" sw.Elapsed.TotalMilliseconds
    0

The test evaluated for 53.5 seconds. For a more detailed analysis I excluded list generation from time measurement:

open MathNet.Symbolics
open Operators

[<EntryPoint>]
let main argv =
    let x = symbol "x"
    let y = symbol "y"

    let terms n= seq {for i in 1..n -> sin(i*x)*cos(i*y)}

    let sw = new System.Diagnostics.Stopwatch()
    let evaledTerms = terms 10_000 |> Seq.toList 
    
    sw.Start()
    let res = evaledTerms |> sum
    sw.Stop()

    printfn "Time %f" sw.Elapsed.TotalMilliseconds
    0

Current time is 53.3 seconds. So the problem is in the sum method.

Expressions.fs shows that sum is realized using reduce:

let sum (xs:Expression list) : Expression = if List.isEmpty xs then zero else List.reduce add xs

So to create a sum of n elements it will call add function n times which is not an effective way to generate large sums.

Is there any "unobvious" method in Symbolics to generate this sum from list without using reduce? Using debugger I can see that the final expression contains a list of terms. Can I generate sum by directly passing a list of terms without creating n temporary accumulators?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant