Given two polynomials and of degree-bound : Multiply and , we get the product with coefficients: Here is also called the Convolution of and (denoted ). If we calculate by multiplying each term in by each term in and then combining terms with equal powers (exactly the old way we learnt in the junior high school), the time complexity would … Continue reading "Polynomial Multiplication"

Read More# Tag: linear-algebra

## Matrix Multiplication: A Programmer’s Perspective

The problem find the nth fibonacci number(A000045) has an optimal solution: matrix multiplication. Similarly, the matrix representation of sequence An = An-1 + An-2 + An-3 (A000073) is: By using matrix multiplication, we can reduce the time complexity from O(n) to O(logn). In linear algebra textbooks, matrix multiplication is the composition of two linear functions. Suppose: Represent … Continue reading "Matrix Multiplication: A Programmer’s Perspective"

Read More