Toeplitz Matrix-Vector Multiply

Problem

Multiply a Toeplitz matrix, given by its first row and first column, by a vector without forming the matrix:

result[i] = sum_j T[i][j] * x[j], where T[i][j] = first_row[j - i] for j >= i and first_col[i - j] otherwise.

Hint

Pick the entry from the first row when the column index is at least the row index.

case 1

in: [[1,2,3],[1,4,5],[1,0,0]]

expected: [1,4,5]

case 2

in: [[1,2,3],[1,4,5],[0,1,0]]

expected: [2,1,4]

case 3

in: [[1,2,3],[1,4,5],[1,1,1]]

expected: [6,7,10]

case 4

in: [[1,2,3],[1,4,5],[0,0,0]]

expected: [0,0,0]

Starter codePython

def toeplitz_matvec(first_row, first_col, x):
    # Your code here
    pass

4 test cases · run your code against them in the editor