Matrix-free linear solve for nullspace I'm looking for an algorithm to solve for the classic:
$$A\mathbf{x} = \mathbf{b}$$
I cannot compute $A$ directly, but rather can compute matrix-vector products $A\mathbf{v}$ for any $\mathbf{v}$.
At first, this appears to be a straightforward application of matrix-free solvers.  Since I don't have any guarantees on symmetry or positive-definitness, this seems like a good application of the BICGSTAB algorithm.
The only problem is that I am interested in the special case where $\mathbf{b} = \mathbf{0}$, i.e. solving for a vector in the nullspace of $A$.  Obviously, the trivial vector $\mathbf{x}$ = $\mathbf{0}$ is a solution, but not an interesting or useful one.  Unfortunately, it's also one that matrix-free methods are prone to find.
(It's also the min-norm solution, which I think is problematic as some solutions search for the min-norm solution.)
Is there any trick I can use to extract a non-trivial solution $\mathbf{x}$ with a matrix-free solver for general $A$?
(Cross-post from math.stackexchange.com; I think this problem is a little more research-y than I originally thought)
 A: Depending on the matrix free method: If it is iterative, you may just initialize it with a nonzero vector $x_0$. For example the Richardson iteration $x_{k+1} = x_k - A^T Ax_k$ does converge to the projection of $x_0$ onto the nullspace of $A$. Inpecting Krylov spaces one should see that something similaria true for Krylov methods like CG.
A: This trick is often used for Markov chains: partition
$$
A = \begin{bmatrix}A_{11} & a_{12} \\ a_{21} & \alpha_{22}\end{bmatrix},
$$
where the partition has sizes $(n-1,1)$, i.e., $\alpha_{22}$ is a scalar and $a_{12}$ and $a_{21}^T$ are single columns. Then, a vector $v = \begin{bmatrix}v_1 \\ 1 \end{bmatrix}$ (partitioned conformably) is in the kernel iff $A_{11}v_1 + a_{12} = 0$. This latter equation is a $(n-1) \times (n-1)$ linear system that you can solve with any matrix-free solver. It is easy to compute the action of $A_{11}$ from that of $A$ given in matrix-free form.
This method works if there exists a vector $v$ in the kernel with nonzero last entry, and if $A_{11}\in\mathbb{R}^{(n-1)\times(n-1)}$ is non-singular. In Markov chains, these properties often follow from connectedness arguments via the Perron-Frobenius theorem. Otherwise, one can permute rows and/or columns to use a different entry than the last.
In any case, the method will fail if $A$ has rank lower than $n-1$, since then $A_{11}$ is necessarily singular. If you know the rank $r$, you can do something similar by setting the last $r$ entries of $v$ to an arbitrary value and solving a system with  $A_{11} \in \mathbb{R}^{(n-r)\times(n-r)}$.
A: A colleague had an idea today that I think works.  We'll test it soon but I'm curious if people here have feedback.
Construct the matrix $B$ where $B$ is $A$ with a row of $1$'s concatenated to the bottom, and vector $\mathbf{c}$ where $\mathbf{c}$ is $\mathbf{x}$ with a $1$ concatenated to the bottom.  This "concatenation" can be done in a matrix-free way, since only the vector-vector product is needed.
Then $B\mathbf{x} = \mathbf{c}$ iff $A\mathbf{x} = \mathbf{b}$ and $\|\mathbf{x}\|_1 = 1$.  The latter condition guarantees that the trivial vector will never be found, and it should always be possible to solve for an $\mathbf{x}$ that satisfies this because any nullspace vector can be arbitrarily rescaled and still remains in the nullspace.  Thus, any solution to $B \mathbf{x} = \mathbf{c}$ is a nontrivial solution of $A\mathbf{x} = \mathbf{0}$.
