Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dot Product of Streaming vectors

  1. Jun 25, 2017 #1
    Hi all,

    Suppose we have vectors coming in order as A, B and then C (but A must be deleted before C comes in). Then how to get the dot product between A and C? It is allowed to store some calculations of A before deleting elements of A, for example, we could store norm of A, dot(A, B) and etc.

    I tried to store (A + B) .^2, (A - B)^2, and then replace B with C, but failed. Please help!!!
     
  2. jcsd
  3. Jun 25, 2017 #2
    Store A in B and then dot B and C.
     
  4. Jun 25, 2017 #3
    Thanks for your reply, it is not allowed to store A in B as B will be used later. Actually, deleting A is to save space.
     
  5. Jun 25, 2017 #4
    In your post you said you are trying to store (A-B)^2 and (A+B)^2. Where are you storing these if space is limited ?
     
  6. Jun 25, 2017 #5
    Sorry, should be square of sum, i.e. store (a_1 + a_2 + ... + a_n - b_1 - b_2 - ... - b_n)^2 and (a_1 + a_2 + ... + a_n + b_1 + b_2 - ... + b_n)^2. These are the values so easy to store.

    Very appreciated if you can help. Thanks.
     
  7. Jun 25, 2017 #6
    So you can store 2 floats at max ?
     
  8. Jun 25, 2017 #7

    jedishrfu

    Staff: Mentor

    Csn you provide some context here? This seems like an arbitrary constraint.
     
  9. Jun 25, 2017 #8
    We can store any value as long as using limited space.
     
  10. Jun 25, 2017 #9
    Ok, here is the context. The incoming large vectors in order are A, B, C. But spaces are limited, to receive vector C, we must delete A first. (B can not be deleted as will be used later.) The problem is how to get the dot (A, C). We are allowed to use extra but limited spaces, for examples, store one or a few intermediate value. Only space constraint.

    Thank a lot.
     
  11. Jun 25, 2017 #10
    My general idea is to store some calculation/calculations between A and B, after replacing B with C, dot (A,C) can be generated from these values. But I can not figure out the details.
     
  12. Jun 25, 2017 #11

    jedishrfu

    Staff: Mentor

    Okay so this is a homework problem given in computer science?
     
  13. Jun 25, 2017 #12
    No, this is not a homework question. Very appreciated if you can help.
     
  14. Jun 25, 2017 #13

    jedishrfu

    Staff: Mentor

    Okay so who placed this constraint on the problem. What are you trying to do here?
     
  15. Jun 25, 2017 #14

    StoneTemplePython

    User Avatar
    Gold Member

    I am inferring that you are operating over Reals (albeit with floating point arithmetic). I am also assuming that these are LARGE vectors, i.e. not say 2 or 3 entries and not overly sparse, and there isn't some other special structure you've omitted.

    Now from here, let's assume each vector has a squared L2 norm = 1. (If this is not the case, you can normalize them and put the actual norms in memo.)

    Now run Gram Schmidt on ##\mathbf a## vs ##\mathbf b##, and get ##\mathbf v##. you now have ##\mathbf v = \mathbf b^{ \parallel a}##.

    you can do ##\mathbf v^T \mathbf c## and adjust scaling to get ##\mathbf a^T \mathbf c##.

    side note: there there is a non-parallelizable, but numerically stable, version of Gram Schmidt that you could use.

    The open question is what you wanted to use ##\mathbf b## for. Depending on uses, the above may or may not work. If for some reason you need all of it, i.e. ##\mathbf b = \mathbf b^{ \parallel a} + \mathbf b^{ \perp a}##, then too bad, I think you're out of luck. If that is the case, it sounds like you're trying to solve for ##\mathbf x## in ##\mathbf {Ax} = \mathbf b##, where ##\mathbf x## and ##\mathbf b## are "big" vectors and ##\mathbf A## is a rank one matrix. In this case, the problem is under specified, like your original post.

    If you merely need to bound the dot product of ##\mathbf a^T \mathbf c## or whatever, you can do bounds with Cauchy Schwartz. But if you are looking to solve... good luck solving a large n-dimensional equation with a rank one matrix.
     
    Last edited: Jun 25, 2017
  16. Jun 25, 2017 #15
    Thanks for your input. But in order to calculate ##\mathbf v^T \mathbf c##, we have to compute and store ##\mathbf v ##, but the problem is that ##\mathbf v ## is a vector and we do not have enough space to store it.
     
  17. Jun 25, 2017 #16

    StoneTemplePython

    User Avatar
    Gold Member

    What I suggested is that you overwrite ##\mathbf b## with ##\mathbf v##, and store any length difference in a memo.

    I should take a step back here. Have you studied linear algebra? Do you understand why you cannot solve for (large) n equations with a rank one matrix?

    Barring some kind of omitted special structure, that's what this problem reduces to.
     
  18. Jun 25, 2017 #17
    Thanks for your reply. Unfortunately, b can not be overwritten as we need to use later.
    I know can we not get a unique solution from Ax = b as you mentioned, so I post the question here. This is problem abstracted from my research, any input is appreciated.
     
  19. Jun 25, 2017 #18
    If the vector only has 2 elements, i.e. A = [a1, a2]; B=[b1, b2]; C=[c1, c2], then we can store two values: v1 = (a1+a2-b1-b2) and v2 = (a1+a2+b1+b2). Then we can get dot (A, C) = 1/4 * ( (v2 - (b1+b2-c1-c2))^2 - (v1 + b1 + b2 - c1 - c2)^2). But if vector is lager than 2, I do not know how to figure it out.
     
  20. Jun 26, 2017 #19

    jedishrfu

    Staff: Mentor

    Closing thread for moderation
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Dot Product of Streaming vectors
  1. Vector Dot Product (Replies: 1)

Loading...