1 /* linbox/blackbox/butterfly.h 2 * Copyright (C) 1999-2001 William J Turner, 3 * 2001 Bradford Hovinen 4 * 5 * Written by William J Turner <wjturner@math.ncsu.edu>, 6 * Bradford Hovinen <hovinen@cis.udel.edu> 7 * 8 * ----------------------------------------------------------- 9 * 2002-09-26 Bradford Hovinen <bghovinen@math.uwaterloo.ca> 10 * 11 * Refactoring: The switch object now only contains the information necessary 12 * for a single 2x2 block. The butterfly black box maintains a vector of switch 13 * objects that it keeps in parallel with its vector of indices. There is a new 14 * lightweight class, called a SwitchFactory, that constructs switches on the 15 * fly. It is defined individually for each switch type, and a instance thereof 16 * is passed to the butterfly, which then uses it to construct its vector. 17 * 18 * This eliminates two problems: first, because switch objects are constructed 19 * by the butterfly itself, there is no need to know a priori the length of the 20 * vector of indices. Second, the switch object itself becomes simpler, as it 21 * need only be responsible for a single 2x2 block. 22 * 23 * ----------------------------------------------------------- 24 * 25 * 26 * ========LICENCE======== 27 * This file is part of the library LinBox. 28 * 29 * LinBox is free software: you can redistribute it and/or modify 30 * it under the terms of the GNU Lesser General Public 31 * License as published by the Free Software Foundation; either 32 * version 2.1 of the License, or (at your option) any later version. 33 * 34 * This library is distributed in the hope that it will be useful, 35 * but WITHOUT ANY WARRANTY; without even the implied warranty of 36 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 37 * Lesser General Public License for more details. 38 * 39 * You should have received a copy of the GNU Lesser General Public 40 * License along with this library; if not, write to the Free Software 41 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 42 * ========LICENCE======== 43 * 44 */ 45 46 #ifndef __LINBOX_butterfly_H 47 #define __LINBOX_butterfly_H 48 49 #include "linbox/blackbox/blackbox-interface.h" 50 #include "linbox/vector/vector-domain.h" 51 52 /*! @file blackbox/butterfly.h 53 */ 54 55 namespace LinBox 56 { 57 58 59 /** The default butterfly switch object. 60 * 61 * This is a predicate object that is applied 62 * to two elements to switch them as needed 63 * by the \ref Butterfly\ Switching\ Network\ BlackBox\ Matrix\ Object 64 * following the exchange matrix introduced in "Efficient Matrix 65 * Preconditioners for Black Box Linear Algebra" by Chen, Eberly, 66 * Kaltofen, Saunders, Turner, and Villard. 67 */ 68 template <class Field> class CekstvSwitch ; 69 70 /// Alternate butterfly switch object for testing. 71 class BooleanSwitch; 72 73 /** @name Butterfly 74 * @brief Butterfly preconditioner and supporting function 75 */ 76 //@{ 77 // 78 /** \brief Switching Network based BlackBox Matrix. A good preconditioner. 79 80 * Implements butterfly switching network on a LinBox vector 81 * as a black box matrix through the use of a switch object. 82 * 83 * This is a blackbox matrix object, and it implements all 84 * purely virtual methods of the abstract base class. 85 * See \ref BlackboxArchetype for the specification of these methods. 86 * 87 * This matrix requires a dense vector to be used. Sparse vectors must 88 * somehow be converted to dense vectors before this matrix may 89 * be applied to them. 90 * 91 * @param Vector LinBox dense vector type 92 * @param Switch switch object type 93 \ingroup blackbox 94 */ 95 template <class _Field, class Switch = CekstvSwitch<_Field>> 96 class Butterfly : public BlackboxInterface { 97 public: 98 typedef _Field Field; 99 typedef Butterfly<_Field, Switch> Self_t; 100 typedef typename Field::Element Element; 101 102 /** No-Op Constructor 103 */ Butterfly(const Field & F,size_t n)104 Butterfly (const Field &F, size_t n) : 105 _field (&F), _VD (F), _n (n) 106 {} 107 108 109 110 /** Constructor from an integer and a switch object. 111 * The switch object is an object that is applied 112 * to two references to elements to switch them. It must have both 113 * an apply and an applyTranspose method. 114 * It must contain all information needed by the switch other 115 * than the elements themselves. This includes any random 116 * numbers or sequences of values. It must also be able to 117 * be applied as many times as needed. In particular, it must be able 118 * to create new random elements or repeat a stored sequence 119 * of values. 120 * This is not required by the abstract base class. 121 * @param n integer size of vectors to be applied to 122 * @param F 123 * @param factory switch predicate object object 124 */ 125 Butterfly (const Field &F, size_t n, typename Switch::Factory &factory); 126 127 /* Destructor. */ ~Butterfly()128 ~Butterfly () {} 129 130 131 /** Application of BlackBox matrix. 132 * <code>y = A*x</code>. 133 * Requires one vector conforming to the \ref LinBox 134 * vector @link Archetypes archetype@endlink. 135 * Required by abstract base class. 136 * For this matrix, this involves applying each switch in order to the 137 * input vector. 138 * @return reference to vector y containing output (after switching). 139 * @param x constant reference to vector to contain input 140 * (before switching) 141 * @param y 142 */ 143 144 template<class OutVector, class InVector> 145 OutVector& apply (OutVector& y, const InVector& x) const; 146 147 /** Application of BlackBox matrix transpose. 148 * <code>y = transpose (A)*x</code>. 149 * Requires one vector conforming to the \ref LinBox 150 * vector @link Archetypes archetype@endlink. 151 * Required by abstract base class. 152 * For this matrix, this involves applying the transpose of each switch 153 * to the input vector in the reverse order of the apply function. 154 * @return reference to vector y containing output (after switching). 155 * @param x constant reference to vector to contain input 156 * (before switching) 157 * @param y 158 */ 159 template<class OutVector, class InVector> 160 OutVector& applyTranspose (OutVector& y, const InVector& x) const; 161 162 template<typename _Tp1, typename _Sw1 = typename Switch::template rebind<_Tp1>::other> 163 struct rebind { 164 typedef Butterfly<_Tp1, _Sw1> other; 165 operatorrebind166 void operator() (other & Ap, const Self_t& A) { 167 // other LAp(F,A._n); 168 Ap.n_vec() = A.n_vec(); 169 Ap.l_vec() = A.l_vec(); 170 Ap.indices() = A.indices(); 171 172 typename std::vector<Switch>::const_iterator sit = A.switchesBegin(); 173 174 for( ; sit != A.switchesEnd(); ++sit) { 175 _Sw1 newsw; 176 typename Switch::template rebind<_Tp1>() (newsw, *sit, Ap.field(), A.field()); 177 Ap.switches().push_back( newsw ); 178 } 179 // Ap = new other(LAp); 180 } 181 }; 182 183 template<typename _Tp1, typename _Sw1> Butterfly(const Butterfly<_Tp1,_Sw1> & B,const Field & F)184 Butterfly (const Butterfly<_Tp1,_Sw1>& B, const Field &F) : 185 _field (&F), _VD (F), _n (B.rowdim()) 186 { 187 typename Butterfly<_Tp1,_Sw1>::template rebind<Field>() (*this, B); 188 } 189 190 191 192 /*- Retreive row dimensions of BlackBox matrix. 193 * This may be needed for applying preconditioners. 194 * Required by abstract base class. 195 * @return integer number of rows of black box matrix. 196 */ rowdim()197 size_t rowdim () const 198 { return _n; } 199 200 /*- Retreive column dimensions of BlackBox matrix. 201 * Required by abstract base class. 202 * @return integer number of columns of black box matrix. 203 */ coldim()204 size_t coldim () const 205 { return _n; } 206 field()207 const Field& field() const 208 {return *_field;} 209 210 211 // Required for rebind 212 // Don't know how to tell that rebind should be friend ... n_vec()213 std::vector<size_t> n_vec() const 214 { return this->_n_vec; } l_vec()215 std::vector<size_t> l_vec() const 216 { return this->_l_vec; } indices()217 std::vector< std::pair< size_t, size_t > > indices() const 218 { return this->_indices; } n_vec()219 std::vector<size_t>& n_vec() { return this->_n_vec; } l_vec()220 std::vector<size_t>& l_vec() { return this->_l_vec; } indices()221 std::vector< std::pair< size_t, size_t > >& indices() { return this->_indices; } switchesBegin()222 typename std::vector<Switch>::const_iterator switchesBegin() const 223 { return this->_switches.begin();} switchesEnd()224 typename std::vector<Switch>::const_iterator switchesEnd() const 225 { return this->_switches.end(); } switches()226 std::vector<Switch>& switches() { return _switches; } 227 228 229 private: 230 231 232 // Field over which we are working 233 const Field *_field; 234 VectorDomain<Field> _VD; 235 236 // Number of rows and columns of square matrix. 237 size_t _n; 238 239 // Vectors of sizes of sub-groups and number of levels in each 240 // These may not need to be stored in general. 241 // They may only be used in the constructor 242 std::vector<size_t> _n_vec, _l_vec; 243 244 // Vector of index pairs. These are the indices to be switched with 245 // a given switch. 246 std::vector< std::pair< size_t, size_t > > _indices; 247 248 // Vector of switches 249 std::vector<Switch> _switches; 250 251 // Build the vector of indices 252 void buildIndices (); 253 254 }; // template <class Field, class Vector> class Butterfly 255 256 /** A function used with Butterfly Blackbox Matrices. 257 * This function takes an STL vector x of booleans, and returns 258 * a vector y of booleans such that setting the switches marked 259 * by true flags in y to be on (or to swap elements) the true 260 * elements x will be switched to a given contiguous block 261 * through the use of a Butterfly switching network. 262 * The integer parameter j marks where this block is to begin. 263 * If x has r true elements, the Butterfly switching network will place 264 * these elements in a contiguous block starting at j and ending at 265 * j + r - 1. 266 * Wrap around shall be considered to preserve contiguity. 267 * The value of j is defaulted to be zero, and it is only allowed to 268 * be non-zero is the size of x is a power of 2. 269 * @return vector of booleans for setting switches 270 * @param x vector of booleans marking elements to switch into 271 * contiguous block 272 * @param j offset of contiguous block 273 */ 274 inline std::vector<bool> setButterfly (const std::vector<bool>& x, 275 size_t j = 0); 276 277 } // namespace LinBox 278 279 #include "butterfly.inl" 280 281 #endif // __LINBOX_butterfly_H 282 283 // Local Variables: 284 // mode: C++ 285 // tab-width: 4 286 // indent-tabs-mode: nil 287 // c-basic-offset: 4 288 // End: 289 // vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s 290