It definitely makes sense, recurrence relation does have its own polynomial. Even the naive polynomial multiplication is very fast.
Now, what I'm wondering is if this is possible to do with adjacency matrices of graphs.
Recently I was calculating the number of paths of a knight going from one position to another in K moves. Ended up doing O(N^6 log K) (N is the chessboard dimension) which was fast enough for a small chessboard but maybe there's a way to turn that adjacency matrix to a polynomial and do the same.
It definitely makes sense, recurrence relation does have its own polynomial. Even the naive polynomial multiplication is very fast.
Now, what I'm wondering is if this is possible to do with adjacency matrices of graphs.
Recently I was calculating the number of paths of a knight going from one position to another in K moves. Ended up doing O(N^6 log K) (N is the chessboard dimension) which was fast enough for a small chessboard but maybe there's a way to turn that adjacency matrix to a polynomial and do the same.