Polynomial Multiplication

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

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