search

fjames86 / fpoly

Manipulate dense multivariate polynomials
0 stars 0 forks source link

lagrange-interpolate #19

Closed fjames86 closed 11 years ago

fjames86 commented 11 years ago

Lagrange-interpolate is very inefficient, in particular it becomes slow very quickly for large number of variables and degree.

A possible solution might be to precompute determinant patterns and at run time to evaluate the patterns with the given set of bindings. e.g. we wish to compute

det((1 2 3) (1 x y) (7 8 9))

we pre compute the det pattern as #{AEI - AFH + EHD - EGC - IFB + IDG} and at run time evalute the pattern with a=1, b=2, c=3, d=1, e=x, f=y g=7 h=8 i=9

This requires improving the fpoly-eval function, which currently is also rather inefficient. see related post for possible improvements for this.

fjames86 commented 11 years ago

since it also needs to compute determinants of very similar matrices, it could reuse some sub-calculations for further speed increases.

fjames86 commented 11 years ago

determinant funcitons are incorrect anyway. this whole section needs a complete overhaul

fjames86 commented 11 years ago

use Gaussian elimination / LU decomposition. it seems like some of the work has already been done in ffge

fjames86 commented 11 years ago

lu demcomp now done, works providing the matrix is non-singular so this probably needs fixing.

write: (lagrange-determinant mat vars row) which computes the polynomial which results from computing the determinant of the matrix with the row-th row replaced with the monomials of the polynomial in vars of degree n (n = row,col size of mat). Can compute this by simply making a polynomial in vars of degree n and setting the coefficients equal to determinants of sub-matrices with appropriate signs. this amounts to first doing a row swap and then computing sub-dets.

fjames86 commented 11 years ago

lu decomposition and determinants added. lagrange-interpolate now seems to be working correctly and not too slowly.