  In this paper, we propose the greedy and random Broyden's method for solving
nonlinear equations. Specifically, the greedy method greedily selects the
direction to maximize a certain measure of progress for approximating the
current Jacobian matrix, while the random method randomly chooses a direction.
We establish explicit (local) superlinear convergence rates of both methods if
the initial point and approximate Jacobian are close enough to a solution and
corresponding Jacobian. Our two novel variants of Broyden's method enjoy two
important advantages that the approximate Jacobians of our algorithms will
converge to the exact ones and the convergence rates of our algorithms are
asymptotically faster than the original Broyden's method. Our work is the first
time to achieve such two advantages theoretically. Our experiments also
empirically validate the advantages of our algorithms.
