Skip to content

fix for dask.array.linalg.tsqr fails tests (intermittently) with arrays of uncertain dimensions#3662

Merged
mrocklin merged 4 commits intodask:masterfrom
convexset:fix-tsqr-case-chunk-with-zero-height
Jun 25, 2018
Merged

fix for dask.array.linalg.tsqr fails tests (intermittently) with arrays of uncertain dimensions#3662
mrocklin merged 4 commits intodask:masterfrom
convexset:fix-tsqr-case-chunk-with-zero-height

Conversation

@convexset
Copy link
Contributor

Fix for issue #3659 where dask.array.linalg.tsqr fails tests with uncertain dimensions (after suitably many runs; test is stochastic)

Cause: uncertain dimensions mean the possibility of chunks with zero height, which np.linalg.qr does not accept

Fix: a wrapper function for np.linalg.qr was written to handle the case

  • Failing tests pass
  • Passes flake8 dask

cause: uncertain dimensions mean the possibility of chunks with zero height, which np.linalg.qr does not accept
fix: a wrapper function for np.linalg.qr was written to handle the case
@mrocklin
Copy link
Member

Thanks @convexset ! I appreciate it. I'm happy to merge this as-is. However, if there is a regression test we can add to make sure that this doesn't happen again that would also be helpful. Given your description, it sounds like maybe this should be something like the following?

nx = np.ones(10, 5)
nq, nr = np.linalg.qr(nx)

x = da.ones((10, 5), chunks=((5, 0, 5), (5,))
q, r = da.linalg.qr(x)

assert_eq(q, nq)
assert_eq(r, nr)

@convexset
Copy link
Contributor Author

Yeah sure, but we can't compare q and nq, and r & nr... we have to check the product and orthogonality. Let me add a test.

…th in the case of known and unknown chunk sizes)
@convexset
Copy link
Contributor Author

Added the requested tests. The tests look at both cases of known and unknown chunk sizes.

@mrocklin
Copy link
Member

The test failures on Travis CI look interesting

@convexset
Copy link
Contributor Author

Very unusual how running it on my own machine (even repeatedly, I don't get the error).

But that said, it looks like something that might depend on the version of numpy that one has... hmmm...

Note: q.chunks is ((4, 0, 1, 0, 5), (5,)) and r.chunks is ((5,), (5,)).

=================================== FAILURES ===================================
_________________________ test_tsqr_zero_height_chunks _________________________
[gw1] linux2 -- Python 2.7.15 /home/travis/miniconda/envs/test-environment/bin/python
    def test_tsqr_zero_height_chunks():
        m_q = 10
        n_q = 5
        m_r = 5
        n_r = 5
    
        # certainty
        mat = np.random.rand(10, 5)
        x = da.from_array(mat, chunks=((4, 0, 1, 0, 5), (5,)))
        q, r = da.linalg.qr(x)
        assert_eq((m_q, n_q), q.shape)  # shape check
        assert_eq((m_r, n_r), r.shape)  # shape check
        assert_eq(mat, da.dot(q, r))  # accuracy check
>       assert_eq(np.eye(n_q, n_q), da.dot(q.T, q))  # q must be orthonormal
dask/array/tests/test_linalg.py:172: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
dask/array/utils.py:83: in assert_eq
    b = b.compute(scheduler='sync')
dask/base.py:156: in compute
    (result,) = compute(self, traverse=False, **kwargs)
dask/base.py:402: in compute
    results = schedule(dsk, keys, **kwargs)
dask/local.py:562: in get_sync
    return get_async(apply_sync, 1, dsk, keys, **kwargs)
dask/local.py:529: in get_async
    fire_task()
dask/local.py:504: in fire_task
    callback=queue.put)
dask/local.py:551: in apply_sync
    res = func(*args, **kwds)
dask/local.py:295: in execute_task
    result = pack_exception(e, dumps)
dask/local.py:290: in execute_task
    result = _execute_task(task, data)
dask/local.py:270: in _execute_task
    args2 = [_execute_task(a, cache) for a in args]
dask/local.py:267: in _execute_task
    return [_execute_task(a, cache) for a in arg]
dask/local.py:271: in _execute_task
    return func(*args2)
dask/array/routines.py:193: in _tensordot
    x = tensordot(a, b, axes=axes)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
a = array([], shape=(5, 0), dtype=float64)
b = array([], shape=(0, 5), dtype=float64), axes = ((1,), (0,))
    def tensordot(a, b, axes=2):
        """
        Compute tensor dot product along specified axes for arrays >= 1-D.
    
        Given two tensors (arrays of dimension greater than or equal to one),
        `a` and `b`, and an array_like object containing two array_like
        objects, ``(a_axes, b_axes)``, sum the products of `a`'s and `b`'s
        elements (components) over the axes specified by ``a_axes`` and
        ``b_axes``. The third argument can be a single non-negative
        integer_like scalar, ``N``; if it is such, then the last ``N``
        dimensions of `a` and the first ``N`` dimensions of `b` are summed
        over.
    
        Parameters
        ----------
        a, b : array_like, len(shape) >= 1
            Tensors to "dot".
    
        axes : int or (2,) array_like
            * integer_like
              If an int N, sum over the last N axes of `a` and the first N axes
              of `b` in order. The sizes of the corresponding axes must match.
            * (2,) array_like
              Or, a list of axes to be summed over, first sequence applying to `a`,
              second to `b`. Both elements array_like must be of the same length.
    
        See Also
        --------
        dot, einsum
    
        Notes
        -----
        Three common use cases are:
            * ``axes = 0`` : tensor product :math:`a\\otimes b`
            * ``axes = 1`` : tensor dot product :math:`a\\cdot b`
            * ``axes = 2`` : (default) tensor double contraction :math:`a:b`
    
        When `axes` is integer_like, the sequence for evaluation will be: first
        the -Nth axis in `a` and 0th axis in `b`, and the -1th axis in `a` and
        Nth axis in `b` last.
    
        When there is more than one axis to sum over - and they are not the last
        (first) axes of `a` (`b`) - the argument `axes` should consist of
        two sequences of the same length, with the first axis to sum over given
        first in both sequences, the second axis second, and so forth.
    
        Examples
        --------
        A "traditional" example:
    
        >>> a = np.arange(60.).reshape(3,4,5)
        >>> b = np.arange(24.).reshape(4,3,2)
        >>> c = np.tensordot(a,b, axes=([1,0],[0,1]))
        >>> c.shape
        (5, 2)
        >>> c
        array([[ 4400.,  4730.],
               [ 4532.,  4874.],
               [ 4664.,  5018.],
               [ 4796.,  5162.],
               [ 4928.,  5306.]])
        >>> # A slower but equivalent way of computing the same...
        >>> d = np.zeros((5,2))
        >>> for i in range(5):
        ...   for j in range(2):
        ...     for k in range(3):
        ...       for n in range(4):
        ...         d[i,j] += a[k,n,i] * b[n,k,j]
        >>> c == d
        array([[ True,  True],
               [ True,  True],
               [ True,  True],
               [ True,  True],
               [ True,  True]], dtype=bool)
    
        An extended example taking advantage of the overloading of + and \\*:
    
        >>> a = np.array(range(1, 9))
        >>> a.shape = (2, 2, 2)
        >>> A = np.array(('a', 'b', 'c', 'd'), dtype=object)
        >>> A.shape = (2, 2)
        >>> a; A
        array([[[1, 2],
                [3, 4]],
               [[5, 6],
                [7, 8]]])
        array([[a, b],
               [c, d]], dtype=object)
    
        >>> np.tensordot(a, A) # third argument default is 2 for double-contraction
        array([abbcccdddd, aaaaabbbbbbcccccccdddddddd], dtype=object)
    
        >>> np.tensordot(a, A, 1)
        array([[[acc, bdd],
                [aaacccc, bbbdddd]],
               [[aaaaacccccc, bbbbbdddddd],
                [aaaaaaacccccccc, bbbbbbbdddddddd]]], dtype=object)
    
        >>> np.tensordot(a, A, 0) # tensor product (result too long to incl.)
        array([[[[[a, b],
                  [c, d]],
                  ...
    
        >>> np.tensordot(a, A, (0, 1))
        array([[[abbbbb, cddddd],
                [aabbbbbb, ccdddddd]],
               [[aaabbbbbbb, cccddddddd],
                [aaaabbbbbbbb, ccccdddddddd]]], dtype=object)
    
        >>> np.tensordot(a, A, (2, 1))
        array([[[abb, cdd],
                [aaabbbb, cccdddd]],
               [[aaaaabbbbbb, cccccdddddd],
                [aaaaaaabbbbbbbb, cccccccdddddddd]]], dtype=object)
    
        >>> np.tensordot(a, A, ((0, 1), (0, 1)))
        array([abbbcccccddddddd, aabbbbccccccdddddddd], dtype=object)
    
        >>> np.tensordot(a, A, ((2, 1), (1, 0)))
        array([acccbbdddd, aaaaacccccccbbbbbbdddddddd], dtype=object)
    
        """
        try:
            iter(axes)
        except:
            axes_a = list(range(-axes, 0))
            axes_b = list(range(0, axes))
        else:
            axes_a, axes_b = axes
        try:
            na = len(axes_a)
            axes_a = list(axes_a)
        except TypeError:
            axes_a = [axes_a]
            na = 1
        try:
            nb = len(axes_b)
            axes_b = list(axes_b)
        except TypeError:
            axes_b = [axes_b]
            nb = 1
    
        a, b = asarray(a), asarray(b)
        as_ = a.shape
        nda = a.ndim
        bs = b.shape
        ndb = b.ndim
        equal = True
        if na != nb:
            equal = False
        else:
            for k in range(na):
                if as_[axes_a[k]] != bs[axes_b[k]]:
                    equal = False
                    break
                if axes_a[k] < 0:
                    axes_a[k] += nda
                if axes_b[k] < 0:
                    axes_b[k] += ndb
        if not equal:
            raise ValueError("shape-mismatch for sum")
    
        # Move the axes to sum over to the end of "a"
        # and to the front of "b"
        notin = [k for k in range(nda) if k not in axes_a]
        newaxes_a = notin + axes_a
        N2 = 1
        for axis in axes_a:
            N2 *= as_[axis]
        newshape_a = (-1, N2)
        olda = [as_[axis] for axis in notin]
    
        notin = [k for k in range(ndb) if k not in axes_b]
        newaxes_b = axes_b + notin
        N2 = 1
        for axis in axes_b:
            N2 *= bs[axis]
        newshape_b = (N2, -1)
        oldb = [bs[axis] for axis in notin]
    
>       at = a.transpose(newaxes_a).reshape(newshape_a)
E       ValueError: cannot reshape array of size 0 into shape (0)
../../../miniconda/envs/test-environment/lib/python2.7/site-packages/numpy/core/numeric.py:1337: ValueError

@convexset
Copy link
Contributor Author

convexset commented Jun 24, 2018

Playing around with numpy==1.13.0 now...

Error reproduced.

@convexset
Copy link
Contributor Author

So I can fix things by having _tensordot at https://github.com/dask/dask/blob/master/dask/array/routines.py#L190 so as to return the right shaped outcome (using np.zeros) in the edge case of a valid tensordot where some contraction axes has size 0 (meaning the two arrays are empty anyway).

…s) in the edge case of a valid tensordot where some contraction axes has size 0
@mrocklin
Copy link
Member

Thanks for following up here @convexset . Merging

@mrocklin mrocklin merged commit 36e235d into dask:master Jun 25, 2018
convexset added a commit to convexset/dask that referenced this pull request Jul 1, 2018
….com/convexset/dask into fix-tsqr-case-chunk-with-zero-height

* 'fix-tsqr-case-chunk-with-zero-height' of https://github.com/convexset/dask:
  fixed typo in documentation and improved clarity
  Implement .blocks accessor (dask#3689)
  Fix wrong names (dask#3695)
  Adds endpoint and retstep support for linspace (dask#3675)
  Add the @ operator to the delayed objects (dask#3691)
  Align auto chunks to provided chunks, rather than shape (dask#3679)
  Adds quotes to source pip install (dask#3678)
  Prefer end-tasks with low numbers of dependencies when ordering (dask#3588)
  Reimplement argtopk to release the GIL (dask#3610)
  Note `da.pad` can be used with `map_overlap` (dask#3672)
  Allow tasks back onto ordering stack if they have one dependency (dask#3652)
  Fix extra progressbar (dask#3669)
  Break apart uneven array-of-int slicing to separate chunks (dask#3648)
  fix for `dask.array.linalg.tsqr` fails tests (intermittently) with arrays of uncertain dimensions (dask#3662)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants