home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15211 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.8 KB  |  40 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!haven.umd.edu!decuac!pa.dec.com!oct17.dfe.dec.com!ryn.mro4.dec.com!gauss.enet.dec.com!roth
  3. From: roth@gauss.enet.dec.com (Jim Roth)
  4. Subject: Re: Bounds on Quadratic Forms ?
  5. Message-ID: <1992Nov18.233826.14983@ryn.mro4.dec.com>
  6. Sender: news@ryn.mro4.dec.com (USENET News System)
  7. Organization: Digital Equipment Corporation
  8. Date: 18 NOV 92 18:35:19    
  9. Lines: 29
  10.  
  11.  
  12. In article <1992Nov5.021547.1@cc.newcastle.edu.au>, eemn@cc.newcastle.edu.au (Brett Ninness) writes...
  13.  
  14. >I have a quadratic form f(x) = x^T A x where x is a positive 
  15. >semidefinite matrix.  I want to know the maximum value
  16. >that f(x) can attain subject to a norm constraint on x.
  17. >Now I know that if the norm I choose is the 2 norm, then
  18. >I can use the Rayleigh-Ritz theorm to bound via
  19. >the maximum eigenvalue of A.  But I want to use the 
  20. >infinity norm.  I know that if I bound the infinity norm
  21. >then I have a bound on the 2 norm and again I
  22. >can use Rayleigh-Ritz, but I want something tighter than
  23. >this.
  24.  
  25. You could test all 2^N cases but I don't think that is too efficient :-)
  26.  
  27. This sounds like it's related to a problem in the geometry of
  28. numbers of finding the shortest vector in a lattice, where it
  29. can be handled by a sequence of unimodular transformations in a pretty
  30. efficient manner.  See, for example, Knuth, Vol II, _The Art of Computer
  31. Programming_, the secton on the spectral test for multiplicative
  32. congruential random number generators.  Another referece is
  33. Zasenhaus & Post _Algorithmic Algebraic Number Theory_ which has a
  34. section on the subject.  I have a few papers at home on efficient
  35. algorithms but don't recall the exact citations off the top of my
  36. head.  I don't think the last word has been spoken on such algorithms,
  37. but the ones out there are not bad.
  38.  
  39. - Jim
  40.