Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem

Abstract

This paper presents criteria for the existence and uniqueness of solution to Kronecker product initial value problem associated with general first order matrix difference system. A modified least square method and a modified QR algorithm are developed to find the best least square solution of the Kronecker product of matrices. Using these methods as a tool the general solution of the Kronecker product initial value problem whose initial condition matrix is over determined is established. Using the method developed by Ishey Haviv and Îded Regev, on finding shortest vector problem we improve further the best least square solution. To boost the hardness factor we simply apply the standard Kronecker product or tensor product of lattices.

Предложен критерий существования и единственности решения задачи кронекеровского произведения с начальными условиями, связанной с обобщенной разностной системой, имеющей матрицу первого порядка. Разработаны модифицированный метод наименьших квадратов и модифицированный QR алгоритм для нахождения наилучшего решения кронекеровского произведения матриц методом наименьших квадратов. Установлено, что при использовании этих методов для общего решения задачи кронекеровского произведения с начальными условиями ее матрица начальных условий является переопределенной. С использованием метода, разработанного Ishey Haviv и Оded Regev, при определении задачи кратчайшего вектора улучшено решение методом наименьших квадратов. Применено стандартное кронекеровское произведение или тензорное произведение на сетках для повышения коэффициента жесткости.

Запропоновано критерій існування та єдиності розв’язку задачі кронекерового добутку з початковими умовами, яка пов’язана з узагальненою різницевою системою, що має матрицю першого порядку. Розроблено модифікований метод найменших квадратів і модифікований QR алгоритм для пошуку найкращого розв’язку кронекерового добутку матриць методом найменших квадратів. Встановлено, що при використанні цих методів для загального розв’язку задачі кронекерового добутку з початковими умовами її матриця початкових умов є переозначеною. З використанням методу, розробленого Ishey Haviv and Оded Regev, при визначенні задачі найкоротшого вектора покращено розв’язок методом найменших квадратів. Застосовано стандартний кронекерів добуток або тензорний добуток на сітках для збільшення коефіцієнта жорсткості.