سوال ۲۸ کنکور ارشد علوم کامپیوتر ۱۴۰۰

Read the following passage and answer the question.

PASSAGE 2: Structure, Sparsity, and Black Boxes

Large matrices of computational interest are simpler than their vast numbers of individual entries might suggest. They have some kind of structure, and as the years have gone by, ways have been found to exploit this structure in more and more contexts.

The most obvious structure that a large matrix may have is sparsity, i.e., a preponderance of zero entries. (The opposite of sparse is dense.) For example, a finite-difference discretization of a partial differential equation may lead to a matrix of dimension $m = 10^{5}$ with only $v = 10$ nonzero entries per row. This kind of structure is readily exploited by the iterative methods we shall discuss, for these algorithms use a matrix in the form of a black box:

$x \longrightarrow \boxed{\text{BLACK BOX}} \longrightarrow Ax.$

The iterative algorithm requires nothing more than the ability to determine $Ax$ for any $x$, which in a computer program will be effected by a procedure whose internal workings need be of no concern to the designer of the iterative algorithm. For the example of a sparse matrix $A$, it is easy to design a procedure to compute $Ax$ in only $O(vm)$ rather than $O(m^{2})$ operations. This is in marked contrast to the algorithms of direct linear algebra, such as Gaussian or Householder triangularization, which explicitly manipulate matrix entries so as to introduce zeros, but in the process generally destroy sparsity.

Question: To compute $Ax$, when $A$ is sparse, an $O(vm)$ algorithm ----------.