Asymptotically Optimal Algorithm for Checking Whether a Given Vector Is a Solution to a Given Interval-Quantifier Linear System

摘要

In many practical situations, we have a linear dependence between different quantities. In such situations, we often need to solve the corresponding systems of linear equations. Often, we know the parameters of these equations with interval uncertainty. In this case, depending on the practical problem, we have different notions of a solution. For example, if we determine parameters from observations, we are interested in all the unknowns which satisfy the given system of linear equations for some possible values of the parameters. If we design a system so that it does not exceed given tolerance bounds, then we need to make sure that for all possible values of the design parameters there exist possible values of the outcome parameters for which the system is satisfied, etc. In general, we can have an arbitrary sequence of quantifiers corresponding to different parameters. The resulting systems are known as interval-quantifier linear systems.In this paper, we provide an asymptotically optimal algorithm for checking whether a given vector is a solution to a given interval-quantifier linear system. For a system of m equations with n unknown, this algorithm takes time O(m * n).