/home/coin/DyLP-1.1.0/DyLP/src/Dylp/vector.h

Go to the documentation of this file.
00001 /*
00002   This file is a part of the OsiDylp LP distribution.
00003  
00004         Copyright (C) 2005 Lou Hafer
00005  
00006         School of Computing Science
00007         Simon Fraser University
00008         Burnaby, B.C., V5A 1S6, Canada
00009         lou@cs.sfu.ca
00010  
00011   This program is free software; you can redistribute it and/or modify it
00012   under the terms of the GNU General Public License as published by the Free
00013   Software Foundation; either version 2 of the License, or (at your option)
00014   any later version.
00015  
00016   This program is distributed in the hope that it will be useful, but WITHOUT
00017   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00018   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
00019   more details.
00020  
00021   You should have received a copy of the GNU General Public License along
00022   with this program; if not, write to the Free Software Foundation, Inc.,
00023   51 Franklin St., Fifth Floor, Boston, MA  02110-1301  USA
00024 */
00025  
00026 #ifndef _DYLP_VECTOR_H
00027 #define _DYLP_VECTOR_H
00028  
00029 /*
00030   @(#)vector.h         4.5         11/06/04
00031   svn/cvs: $Id: vector.h 98 2006-07-03 00:53:56Z lou $
00032 */
00033 
00034 #include <DylpConfig.h>
00035  
00036 /*
00037   Why, you might ask, are we including ctype.h? Well, it's required by the
00038   ANSI C specification, so it's pretty well guaranteed to exist. And, at least
00039   in Solaris and Linux environments that I'm familiar with, it'll pull in the
00040   compile-time symbols that specify big- or little-endian, which we really
00041   want.
00042 */
00043 #include <ctype.h>
00044  
00045 /*
00046   A bunch of standard definitions.
00047 */
00048 #include "dylib_std.h"
00049  
00050 /*
00051   In a few rare instances, the declarations here will be unused, but for dylp
00052   this is a good bet.
00053 */
00054 #include <math.h>
00055 
00056 /*
00057   Some subset of these will work on any system. Check config_dylp.h to see
00058   which ones are actually in use.
00059 */
00060 #ifdef HAVE_FLOAT_H
00061 # include <float.h>
00062 #endif
00063 #ifdef HAVE_IEEEFP_H
00064 # include <ieeefp.h>
00065 #endif
00066 #ifdef HAVE_SUNMATH_H
00067 # include <sunmath.h>
00068 #endif
00069 
00070  
00071 /*
00072   The Theory: quiet_nan is used to indicate failure (by returning NaN)
00073   without triggering a signal the client may not be prepared to catch. The
00074   idea is that any reasonable checks in the client will detect NaN fairly
00075   quickly.  signalling_nan is used when there's no advantage in delaying a
00076   signal.
00077  
00078   The Reality: Neither seems to trigger a signal, and many computing
00079   environments can't tell the difference. But it's coded into dylp, and it'd
00080   be much ado to change. Hence the compile-time ugliness that follows.
00081  
00082   In the Sun Workshop environment, quiet_nan and signalling_nan are declared
00083   in sunmath.h and found in libsunmath. With release 5.0, sunmath.h includes
00084   some declarations of type `long long', which isn't supported under the -Xc
00085   (strict ANSI compatibility) option for cc. So, we extract only the
00086   definitions we need.  Unfortunately, sunmath.h is present only in the Sun
00087   Workshop programming environment. Sun without Workshop has only the
00088   require file nan.h, which is inadequate.
00089  
00090   For a long while, GNU C didn't distinguish QNaN and SNaN. More recently,
00091   its support for IEEE 754 seems to have improved, but it's not clear that we
00092   can count on everyone having a recent GCC environment just yet. Here, too,
00093   nan.h is inadequate.  The easy way out is to simply #define them as macros
00094   that return the proper bit pattern. Arguably this would make more sense in
00095   general than Sun's implementation as functions.
00096  
00097   According to IEEE 754, the proper bit patterns are:
00098  
00099     0x7ff00000 00000000                  for Inf
00100     0x7fffffff ffffffff                  for QNaN
00101     0x7ff00000 00000001                  for SNaN
00102    
00103   It works this way: The IEEE definition of NaN is
00104     Bits         Value
00105     63                  sign --- don't care for a NaN, but nice to be positive (0)
00106     62:52         exponent --- must be maximum value, 0x7ff
00107     51:0         fraction --- must not be zero (a fraction of zero is the
00108                   representation of infinity). Sun documentation defines QNaN
00109                   as having bit 51 of the fraction set to 1, SNaN as having
00110                   bit 51 set to 0.
00111  
00112   Creating the proper constants qualifies as a serious gross hack. And if you
00113   have a little-endian machine (the 80x86 family being far and away the most
00114   common example), you need to flip the byte order.
00115 */
00116   typedef union { unsigned char fpchr[8] ; double fpdbl ; } fpunion_t ;
00117 /*
00118   Yes, all this really is needed to get all the various compilers to quit
00119   complaining. We need the `(unsigned char)' to prevent some compilers from
00120   complaining about the initialiser being out of range. Goes to the ANSI C
00121   rule that `Character constants not preceded by the letter L have type int.'
00122 */
00123 #ifdef WORDS_BIGENDIAN
00124     static fpunion_t QNaNbits UNUSED = { { (unsigned char) '\177',
00125                                         (unsigned char) '\377',
00126                                         (unsigned char) '\377',
00127                                         (unsigned char) '\377',
00128                                         (unsigned char) '\377',
00129                                         (unsigned char) '\377',
00130                                         (unsigned char) '\377',
00131                                         (unsigned char) '\376' } } ;
00132     static fpunion_t SNaNbits UNUSED = { { (unsigned char) '\177',
00133                                         (unsigned char) '\360',
00134                                         (unsigned char) '\0',
00135                                         (unsigned char) '\0',
00136                                         (unsigned char) '\0',
00137                                         (unsigned char) '\0',
00138                                         (unsigned char) '\0',
00139                                         (unsigned char) '\001' } } ;
00140     static fpunion_t Infbits UNUSED = { { (unsigned char) '\177',
00141                                        (unsigned char) '\360',
00142                                        (unsigned char) '\0',
00143                                        (unsigned char) '\0',
00144                                        (unsigned char) '\0',
00145                                        (unsigned char) '\0',
00146                                        (unsigned char) '\0',
00147                                        (unsigned char) '\0' } } ;
00148 #else
00149     static fpunion_t QNaNbits UNUSED = { { (unsigned char) '\376',
00150                                         (unsigned char) '\377',
00151                                         (unsigned char) '\377',
00152                                         (unsigned char) '\377',
00153                                        (unsigned char) '\377',
00154                                         (unsigned char) '\377',
00155                                         (unsigned char) '\377',
00156                                         (unsigned char) '\177' } } ;
00157     static fpunion_t SNaNbits UNUSED = { { (unsigned char) '\001',
00158                                         (unsigned char) '\0',
00159                                         (unsigned char) '\0',
00160                                         (unsigned char) '\0',
00161                                         (unsigned char) '\0',
00162                                         (unsigned char) '\0',
00163                                         (unsigned char) '\360',
00164                                         (unsigned char) '\177' } } ;
00165     static fpunion_t Infbits UNUSED = { { (unsigned char) '\0',
00166                                        (unsigned char) '\0',
00167                                        (unsigned char) '\0',
00168                                        (unsigned char) '\0',
00169                                        (unsigned char) '\0',
00170                                        (unsigned char) '\0',
00171                                        (unsigned char) '\360',
00172                                        (unsigned char) '\177' } } ;
00173 #endif /* WORDS_BIGENDIAN */
00174 
00175 /*
00176   If we didn't find a quiet_nan function, fake it with a macro.
00177 */
00178 
00179 #ifndef DYLP_HAS_QUIET_NAN
00180 # define quiet_nan(zz_dummy_zz) (QNaNbits.fpdbl)
00181 #endif 
00182 
00183 /*
00184   On some machines, HUGE_VAL isn't actually IEEE infinity. Fix that if
00185   necessary.
00186   AW: I just overwrite this now everytime, since the result should be
00187           the same.
00188 */
00189  
00190 #undef HUGE_VAL
00191 #define HUGE_VAL (Infbits.fpdbl)
00192 
00193 /*
00194   In a Sun/Solaris environment, the definitions and functions that support
00195   IEEE floating point are in ieeefp.h. This seems to be true even if GNU
00196   compilers are being used instead of Sun Workshop compilers. In a GNU/Linux
00197   environment, the necessary definitions seem to live in math.h. The upshot
00198   is that we need to explicitly pull in ieeefp.h here for a Sun environment.
00199  
00200   In a Microsoft environment the correct functions look to be _finite and
00201   _isnan from float.h.
00202 
00203   Assign the proper names to finite and isnan, based on the values deduced by
00204   configure. Again, check config_dylp to see the actual names. If either name
00205   is already defined, bet that it's the correct definition.
00206 */
00207 
00208 #ifndef finite
00209 # define finite DYLP_ISFINITE
00210 #endif
00211 #ifndef isnan
00212 # define isnan  DYLP_ISNAN
00213 #endif
00214  
00215  
00216 /*
00217   Packed Vectors
00218  
00219   The packed vector type consists of a header plus an array of <index, value>
00220   pairs for the non-default entries of the vector.
00221  
00222   pkcoeff_struct
00223  
00224   Field                  Description
00225   -----                  -----------
00226   ndx                  the column/row index for the coefficient
00227   val                  the value of the coefficient
00228  
00229   pkvec_struct
00230  
00231   Field                  Description
00232   -----                  -----------
00233   ndx                  the common index for all coefficients when the vector is a
00234                   row or column from a matrix
00235   nme                  name associated with this vector, if any
00236   dim                  length of the vector when unpacked
00237   dflt                  the default value of coefficients not in coeffs
00238   cnt                  number of non-default coefficients in the coeffs array
00239   sze                  allocated capacity (in pkcoeff_struct's) of the coeffs array
00240   coeffs         the array of (column/row index, coefficient) pairs
00241  
00242   NOTE: pkvec_struct->coeffs is indexed from 0 and sized accordingly.
00243 */
00244  
00245 typedef struct { int ndx ;
00246                    double val ; } pkcoeff_struct ;
00247  
00248 typedef struct { int ndx ;
00249                    const char *nme ;
00250                    int dim ;
00251                    double dflt ;
00252                    int cnt ;
00253                    int sze ;
00254                    pkcoeff_struct *coeffs ; } pkvec_struct ;
00255  
00256 pkvec_struct *pkvec_new(int sze) ;
00257 bool pkvec_resize(pkvec_struct *pkvec, int sze) ;
00258 void pkvec_free(pkvec_struct *pkvec) ;
00259  
00260 bool pkvec_check(pkvec_struct *pkvec, const char *caller) ;
00261  
00262 double pkvec_2norm(pkvec_struct *vec) ;
00263  
00264 double exvec_1norm(double *vec, int len),
00265        exvec_ssq(double *vec, int len),
00266        exvec_2norm(double *vec, int len),
00267        exvec_infnorm(double *vec, int len, int *p_jmax) ;
00268  
00269 double pkvec_dotexvec(pkvec_struct *pkvec, double *exvec) ;
00270  
00271 #endif /* _DYLP_VECTOR_H */

Generated on Wed Aug 22 05:43:40 2007 by  doxygen 1.4.7