Найти один неправильный элемент в матричном продукте?

Даны три матрицы N * N A, B, C. C - это то же самое, что и произведение A и B, за исключением того, что ровно один элемент является неправильным. Наивный алгоритм для его поиска требует N ^ 3 раз. Можем ли мы сделать это быстрее?

Ответы

Ответ 1

Возьмите вектор v = (1 1 1 1 ... 1)T и вычислите: u = Cv - A(Bv).

u равно (C-AB)v, и поэтому он будет иметь нули во всех элементах, кроме одного. Индекс этого элемента соответствует индексу строки, где C отличается от AB. Значение элемента (a) - это значение ненулевого элемента в C-AB.

Чтобы найти индекс столбца, вы можете повторить это с помощью вектора v2 = (1 2 3 4 ... n)T. Теперь значение ненулевого элемента ac, где a - это значение, которое мы рассчитали ранее, и c - индекс столбца.

Поскольку мы выполняем только несколько векторных умножений матрицы *, время работы равно O (n ^ 2).