search

QuantEcon / BasisMatrices.jl

Routines for constructing BasisMatrices of different types (Chebyshev polynomials, B-Splines, piecewise linear, complete monomials, Smolyak...)
BSD 3-Clause "New" or "Revised" License
32 stars 22 forks source link

status? #21

Closed sglyon closed 7 years ago

sglyon commented 8 years ago

Issue by floswald Monday Dec 14, 2015 at 10:55 GMT Originally opened as https://github.com/QuantEcon/CompEcon.jl/issues/21

Hi @spencerlyon2

how are you doing with this? I can see you are being very active in many places, Interpolations.jl for example, what's your feeling about this project here? I think it would be great to have a unifying framework a la CompEcon. I'm not saying this is necessarily the best way to achieve this, but it is a solid start. I like that one can construct different interpolations by just giving a different keyword. What about pulling your Smolyak package into this here? This is nothing else than a different way of constructing a basis function, so should fit well with the setup here.

sglyon commented 8 years ago

Comment by spencerlyon2 Monday Dec 14, 2015 at 14:42 GMT

Hey @floswald thanks for reaching out.

The code here is a complete Julia version of the function approximation and quadrature parts of the Matlab compecon.

Relative to Interpolations.jl I think there are two main advantages here:

That being said, the biggest disadvantage of CompEcon.jl is performance. For evaluating at many points at a time in only a few dimensions, this library comes pretty close to Interpolations.jl performance (close enough to make it usable). However, if you start evaluating a fewer points or more dimensions, Interpolations outperforms us by a large margin (up to 100x in some research code I have).

The main performance issues come from our underlying use of the sparse(I, J, V) function to construct a SparseMatrixCSC when using spline interpolation. Last time I checked we were spending up to 90-95% of our time in that one Base Julia function. This is something we can get around (by constructing colptr, rowval, nzval instead of (i, j) -> v triplets), but I haven't taken the time because Interpolations.jl functionality was sufficient for my needs at the time.

Adding my Smolyak code here shouldn't be very hard and would be a good addition. I don't have the extra cycles to do that myself right now, but I am definitely open to this idea.

I think the function approximation bits here are not unrealted to ApproXD.jl. How is that project going? Are you looking to collaborate to push econ tools forward?

sglyon commented 8 years ago

Comment by floswald Monday Dec 14, 2015 at 15:50 GMT

Spencer,

sounds good. I wasn't aware of such large performance losses when doing pointwise interpolations. I've been following Interpolations.jl with amazement. I have got no idea how they get it that fast. They are taking the full tensor product when evaluating a, say, 4D function space, right? I was trying to understand whether they construct a sparse spline basis and sum only over those, but that's not what I found. But maybe I wasn't looking in the right spot. Anyway, things like the Smolyak are missing from pretty much anywhere, so would be great to have it here. ApproXD.jl was written long before one could supply irregular grids to any of the packages available now - at the time there was only Grids.jl, with regular grids. I never actually used the spline interpolation, only always the linear interpolator. All in all quite low tech, but it did the job. It seems to be doing much worse than Interpolations.jl in the high throughput tests, and I'm not keen on spending too much time finding out why - so will probably leave this as it is at the moment.

Anyway, I would be happy to integrate that somewhere (although really it's very similar to many things out there), our place under an organisation or whatever. There may be certain user cases where it's useful, who knows. So yes, I would be happy to collaborate in this sense, and also the one and other odd PR if need be.

Keep up the good work! See you around

On 14 December 2015 at 15:42, Spencer Lyon notifications@github.com wrote:

Hey @floswald https://github.com/floswald thanks for reaching out.

The code here is a complete Julia version of the function approximation and quadrature parts of the Matlab compecon.

Relative to Interpolations.jl I think there are two main advantages here:

  • Flexibility: This code is quite flexible and allows you to mix and match different interpolation frameworks per dimension (Chebyshev, b-splines, piecewise linear). Interpolations.jl is only b-splines.
  • Access to raw basis matrices: By this I mean a matrix that is N_points by N_basis_function matrix that evaluates each basis function at each user-desired point. Access to this matrix is a crucial part of a few of my algorithms and there is no way to get it out of Interpolations.jl as it currently stands.

That being said, the biggest disadvantage of CompEcon.jl is performance. For evaluating at many points at a time in only a few dimensions, this library comes pretty close to Interpolations.jl performance (close enough to make it usable). However, if you start evaluating a fewer points or more dimensions, Interpolations outperforms us by a large margin (up to 100x in some research code I have).

The main performance issues come from our underlying use of the sparse(I, J, V) function to construct a SparseMatrixCSC when using spline interpolation. Last time I checked we were spending up to 90-95% of our time in that one Base Julia function. This is something we can get around (by constructing colptr, rowval, nzval instead of (i, j) -> v triplets), but I haven't taken the time because Interpolations.jl functionality was sufficient for my needs at the time.

Adding my Smolyak code here shouldn't be very hard and would be a good addition. I don't have the extra cycles to do that myself right now, but I am definitely open to this idea.

I think the function approximation bits here are not unrealted to ApproXD.jl. How is that project going? Are you looking to collaborate to push econ tools forward?

— Reply to this email directly or view it on GitHub https://github.com/spencerlyon2/CompEcon.jl/issues/21#issuecomment-164454233 .