home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / apl / 955 < prev    next >
Encoding:
Text File  |  1992-08-17  |  1.2 KB  |  27 lines
  1. Newsgroups: comp.lang.apl
  2. Path: sparky!uunet!s5!sethb
  3. From: sethb@fid.morgan.com (Seth Breidbart)
  4. Subject: Re: Numerical Analysis + APL/J
  5. Message-ID: <1992Aug17.165305.2364@fid.morgan.com>
  6. Organization: Morgan Stanley & Co., New York, NY
  7. References: <1169@kepler1.rentec.com> <1992Aug14.032619.16083@yrloc.ipsa.reuter.COM> <1177@kepler1.rentec.com>
  8. Date: Mon, 17 Aug 1992 16:53:05 GMT
  9. Lines: 16
  10.  
  11. In article <1177@kepler1.rentec.com> andrew@rentec.com (Andrew Mullhaupt) writes:
  12. >In article <1992Aug14.032619.16083@yrloc.ipsa.reuter.COM> hui@yrloc.ipsa.reuter.COM (Roger Hui) writes:
  13. >
  14. >>[Aside:  You say, "It can't".  I believe it would be quite difficult to
  15. >>prove that QR can't be done in time O(n^2) (or O(m*n) on an (m,n) matrix).]
  16. >
  17. >How about an oracle argument. Suppose you guess Q and R in O(1). You
  18. >have to then verify it by checking that R is upper triangular, 
  19. >and then you must verify that Q is (column) orthogonal. You don't have
  20. >to check the lower triangle of QTQ, but this leaves O(n^2) things to check.
  21.  
  22. I can generate the "group operation matrix" for the integers mod n
  23. under addition in time n^2; you can't check an arbitrary nxn matrix to
  24. see if it's a group that fast.
  25.  
  26. Seth        sethb@fid.morgan.com
  27.