|
BWAPI
|
00001 // Copyright (c) 2008 Max-Planck-Institute Saarbruecken (Germany). 00002 // All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or 00005 // modify it under the terms of the GNU Lesser General Public License as 00006 // published by the Free Software Foundation; version 2.1 of the License. 00007 // See the file LICENSE.LGPL distributed with CGAL. 00008 // 00009 // Licensees holding a valid commercial license may use this file in 00010 // accordance with the commercial license agreement provided with the software. 00011 // 00012 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00013 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00014 // 00015 // $URL: svn+ssh://afabri@scm.gforge.inria.fr/svn/cgal/trunk/Polynomial/include/CGAL/Polynomial.h $ 00016 // $Id: Polynomial.h 46502 2008-10-28 08:36:59Z hemmer $ 00017 // 00018 // Author(s) : Michael Kerber <mkerber@mpi-inf.mpg.de> 00019 // 00020 // ============================================================================ 00021 #ifndef CGAL_POLYNOMIAL_SUBRESULTANTS_H 00022 #define CGAL_POLYNOMIAL_SUBRESULTANTS_H 00023 00024 #include <list> 00025 00026 #include <CGAL/Polynomial_traits_d.h> 00027 #include <CGAL/Polynomial/bezout_matrix.h> 00028 00029 CGAL_BEGIN_NAMESPACE 00030 00031 00032 namespace CGALi { 00033 00034 // Intern function needed for Ducos algorithm 00035 00036 template<typename Polynomial_traits_d> void lazard_optimization 00037 (typename Polynomial_traits_d::Coefficient_type y, 00038 double n, 00039 typename Polynomial_traits_d::Polynomial_d B, 00040 typename Polynomial_traits_d::Polynomial_d& C) { 00041 00042 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00043 typedef typename Polynomial_traits_d::Coefficient_type NT; 00044 typename CGAL::Algebraic_structure_traits<NT>::Integral_division idiv; 00045 00046 CGAL_precondition(n>0); 00047 NT x = typename Polynomial_traits_d::Leading_coefficient() (B); 00048 double a = pow(2.,std::floor(log(n)/log(2.))); 00049 NT c = x; 00050 n -= a; 00051 while(a!=1) { 00052 a/=2; 00053 c=idiv(c*c,y); 00054 if(n>=a) { 00055 c=idiv(c*x,y); 00056 n-=a; 00057 } 00058 } 00059 C=c*B/y; 00060 } 00061 00062 template<typename Polynomial_traits_d> 00063 void lickteig_roy_optimization 00064 (typename Polynomial_traits_d::Polynomial_d A, 00065 typename Polynomial_traits_d::Polynomial_d B, 00066 typename Polynomial_traits_d::Polynomial_d C, 00067 typename Polynomial_traits_d::Coefficient_type s, 00068 typename Polynomial_traits_d::Polynomial_d& D) { 00069 00070 typedef typename Polynomial_traits_d::Polynomial_d Poly; 00071 typedef typename Polynomial_traits_d::Coefficient_type NT; 00072 typename Polynomial_traits_d::Degree degree; 00073 typename Polynomial_traits_d::Leading_coefficient lcoeff; 00074 typename Polynomial_traits_d::Construct_polynomial construct; 00075 typename Polynomial_traits_d::Get_coefficient coeff; 00076 00077 int d = degree(A), e = degree(B); 00078 CGAL_precondition(d>=e); 00079 std::vector<Poly> H(d+1); 00080 std::list<NT> initial; 00081 initial.push_front(lcoeff(C)); 00082 for(int i=0;i<e;i++) { 00083 H[i] = construct(initial.begin(),initial.end()); 00084 initial.push_front(NT(0)); 00085 } 00086 H[e]=construct(initial.begin(),initial.end())-C; 00087 CGAL_assertion(degree(H[e])<e); 00088 initial.clear(); 00089 std::copy(H[e].begin(),H[e].end(),std::back_inserter(initial)); 00090 initial.push_front(NT(0)); 00091 for(int i=e+1;i<d;i++) { 00092 H[i]=construct(initial.begin(),initial.end()); 00093 NT h_i_e=H[i].degree()>=e ? coeff(H[i],e) : NT(0); 00094 H[i]-=(h_i_e*B)/lcoeff(B); 00095 initial.clear(); 00096 std::copy(H[i].begin(),H[i].end(),std::back_inserter(initial)); 00097 initial.push_front(NT(0)); 00098 } 00099 H[d]=construct(initial.begin(),initial.end()); 00100 D=construct(0); 00101 for(int i=0;i<d;i++) { 00102 D+=A[i]*H[i]; 00103 } 00104 D/=lcoeff(A); 00105 NT Hde = degree(H[d])>=e ? coeff(H[d],e) : NT(0); 00106 D=(lcoeff(B)*(H[d]+D)-Hde*B)/s; 00107 if((d-e)%2==0) { 00108 D=-D; 00109 } 00110 return; 00111 } 00112 00113 template<typename Polynomial_traits_d> 00114 typename Polynomial_traits_d::Coefficient_type 00115 resultant_for_constant_polynomial 00116 (typename Polynomial_traits_d::Polynomial_d P, 00117 typename Polynomial_traits_d::Polynomial_d Q) { 00118 00119 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00120 typedef typename Polynomial_traits_d::Coefficient_type NT; 00121 typename Polynomial_traits_d::Leading_coefficient lcoeff; 00122 typename Polynomial_traits_d::Degree degree; 00123 typename CGAL::Algebraic_structure_traits<Polynomial>::Is_zero is_zero; 00124 CGAL_assertion(degree(P) < 1 || degree(Q) < 1); 00125 if(is_zero(P) || is_zero(Q) ) { 00126 return NT(0); 00127 } 00128 if(degree(P)==0) { 00129 return CGAL::ipower(lcoeff(P),degree(Q)); 00130 } else { 00131 return CGAL::ipower(lcoeff(Q),degree(P)); 00132 } 00133 } 00134 00135 00145 template <typename Polynomial_traits_d,typename OutputIterator> inline 00146 OutputIterator prs_polynomial_subresultants 00147 (typename Polynomial_traits_d::Polynomial_d P, 00148 typename Polynomial_traits_d::Polynomial_d Q, 00149 OutputIterator out) { 00150 00151 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00152 typedef typename Polynomial_traits_d::Coefficient_type NT; 00153 typename Polynomial_traits_d::Leading_coefficient lcoeff; 00154 typename Polynomial_traits_d::Degree degree; 00155 typename Polynomial_traits_d::Construct_polynomial construct; 00156 typename CGAL::Algebraic_structure_traits<Polynomial>::Is_zero is_zero; 00157 00158 if(degree(P) < 1 || degree(Q) < 1) { 00159 *out++ = CGAL::CGALi::resultant_for_constant_polynomial 00160 <Polynomial_traits_d> (P,Q); 00161 return out; 00162 } 00163 00164 bool poly_swapped = (degree(P) < degree(Q)); 00165 00166 if(poly_swapped) { 00167 std::swap(P,Q); 00168 } 00169 00170 Polynomial zero_pol = construct(NT(0)); 00171 std::vector<Polynomial> sres; 00172 00173 int deg_diff=degree(P)-degree(Q); 00174 00175 if(deg_diff==0) { 00176 sres.push_back(Q); 00177 } else { 00178 sres.push_back(CGAL::ipower(lcoeff(Q),deg_diff-1)*Q); 00179 } 00180 00181 Polynomial A,B,C,D,dummy_pol; 00182 NT s,dummy_nt; 00183 int delta,d,e; 00184 00185 A=Q; 00186 00187 s=CGAL::ipower(lcoeff(Q),deg_diff); 00188 00189 typename Polynomial_traits_d::Pseudo_division() 00190 (P, -Q, dummy_pol, B, dummy_nt); 00191 00192 while(true) { 00193 d=degree(A); 00194 e=degree(B); 00195 if(is_zero(B)) { 00196 for(int i=0;i<d;i++) { 00197 sres.push_back(zero_pol); 00198 } 00199 break; 00200 } 00201 sres.push_back(B); 00202 delta=d-e; 00203 if(delta>1) { 00204 CGAL::CGALi::lazard_optimization<Polynomial_traits_d> 00205 (s,double(delta-1),B,C); 00206 //C=CGAL::ipower(CGAL::integral_division(lcoeff(B),s),delta-1)*B; 00207 for(int i=0;i<delta-2;i++) { 00208 sres.push_back(zero_pol); 00209 } 00210 sres.push_back(C); 00211 } 00212 else { 00213 C=B; 00214 } 00215 if(e==0) { 00216 break; 00217 } 00218 CGAL::CGALi::lickteig_roy_optimization<Polynomial_traits_d>(A,B,C,s,D); 00219 B=D; 00220 //typename Polynomial_traits_d::Pseudo_division() 00221 // (A, -B, dummy_pol, D, dummy_nt); 00222 //B= D / (CGAL::ipower(s,delta)*lcoeff(A)); 00223 A=C; 00224 s=lcoeff(A); 00225 } 00226 00227 CGAL_assertion(static_cast<int>(sres.size()) 00228 == degree(Q)+1); 00229 00230 // If P and Q were swapped, correct the signs 00231 if(poly_swapped) { 00232 int p = degree(P); 00233 int q = degree(Q); 00234 for(int i=0;i<=q;i++) { 00235 if((p-i)*(q-i) % 2 == 1) { 00236 sres[q-i]=-sres[q-i]; 00237 } 00238 } 00239 } 00240 00241 // Now, reverse the entries 00242 return std::copy(sres.rbegin(),sres.rend(),out); 00243 } 00244 00245 00250 template <typename Polynomial_traits_d,typename OutputIterator> inline 00251 OutputIterator bezout_polynomial_subresultants 00252 (typename Polynomial_traits_d::Polynomial_d P, 00253 typename Polynomial_traits_d::Polynomial_d Q, 00254 OutputIterator out) { 00255 00256 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00257 typedef typename Polynomial_traits_d::Coefficient_type NT; 00258 typename Polynomial_traits_d::Leading_coefficient lcoeff; 00259 typename Polynomial_traits_d::Degree degree; 00260 typename Polynomial_traits_d::Construct_polynomial construct; 00261 00262 if(degree(P) < 1 || degree(Q) < 1) { 00263 *out++ = CGAL::CGALi::resultant_for_constant_polynomial 00264 <Polynomial_traits_d> (P,Q); 00265 return out; 00266 } 00267 00268 typedef CGAL::CGALi::Simple_matrix<NT> Matrix; 00269 Matrix M = CGAL::CGALi::polynomial_subresultant_matrix 00270 <Polynomial_traits_d> (P,Q); 00271 00272 int r = static_cast<int>(M.row_dimension()); 00273 00274 for(int i = 0;i < r; i++) { 00275 std::vector<NT> curr_row; 00276 std::copy(M[r-1-i].begin(), 00277 M[r-1-i].end(), 00278 std::back_inserter(curr_row)); 00279 //std::reverse(curr_row.begin(),curr_row.end()); 00280 *out++ = construct(curr_row.rbegin(),curr_row.rend()); 00281 } 00282 int deg_diff=degree(P)-degree(Q); 00283 if(deg_diff==0) { 00284 *out++=Q; 00285 } else if(deg_diff>0) { 00286 *out++=CGAL::ipower(lcoeff(Q),deg_diff-1)*Q; 00287 } else { 00288 *out++=CGAL::ipower(lcoeff(P),-deg_diff-1)*P; 00289 } 00290 00291 return out; 00292 00293 } 00294 00302 template <typename Polynomial_traits_d,typename OutputIterator> inline 00303 OutputIterator prs_principal_subresultants 00304 (typename Polynomial_traits_d::Polynomial_d P, 00305 typename Polynomial_traits_d::Polynomial_d Q, 00306 OutputIterator out) { 00307 00308 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00309 typedef typename Polynomial_traits_d::Coefficient_type NT; 00310 typename Polynomial_traits_d::Degree degree; 00311 typename Polynomial_traits_d::Get_coefficient coeff; 00312 00313 std::vector<Polynomial> sres; 00314 int q = std::min(degree(Q),degree(P)); 00315 00316 CGAL::CGALi::prs_polynomial_subresultants<Polynomial_traits_d> 00317 (P,Q,std::back_inserter(sres)); 00318 CGAL_assertion(static_cast<int>(sres.size()) == q+1); 00319 for(int i=0; i <= q; i++) { 00320 int d = degree(sres[i]); 00321 CGAL_assertion(d<=i); 00322 if(d<i) { 00323 *out++ = NT(0); 00324 } else { 00325 *out++ = coeff(sres[i],i); 00326 } 00327 } 00328 return out; 00329 } 00330 00336 template <typename Polynomial_traits_d,typename OutputIterator> inline 00337 OutputIterator bezout_principal_subresultants 00338 (typename Polynomial_traits_d::Polynomial_d P, 00339 typename Polynomial_traits_d::Polynomial_d Q, 00340 OutputIterator out) { 00341 00342 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00343 typedef typename Polynomial_traits_d::Coefficient_type NT; 00344 typename Polynomial_traits_d::Leading_coefficient lcoeff; 00345 typename Polynomial_traits_d::Degree degree; 00346 00347 if(degree(P) < 1 || degree(Q) < 1) { 00348 *out++ = CGAL::CGALi::resultant_for_constant_polynomial 00349 <Polynomial_traits_d> (P,Q); 00350 return out; 00351 } 00352 00353 typedef CGAL::CGALi::Simple_matrix<NT> Matrix; 00354 Matrix M = CGAL::CGALi::polynomial_subresultant_matrix 00355 <Polynomial_traits_d> (P,Q,1); 00356 00357 int r = static_cast<int>(M.row_dimension()); 00358 00359 for(int i = r - 1;i >=0; i--) { 00360 *out++=M[i][i]; 00361 } 00362 int deg_diff=degree(P)-degree(Q); 00363 if(deg_diff==0) { 00364 *out++=NT(1); 00365 } else if(deg_diff>0) { 00366 *out++=CGAL::ipower(lcoeff(Q),deg_diff); 00367 } else { 00368 *out++=CGAL::ipower(lcoeff(P),-deg_diff); 00369 } 00370 return out; 00371 00372 } 00373 00380 template<typename Polynomial_traits_d, 00381 typename OutputIterator1, 00382 typename OutputIterator2, 00383 typename OutputIterator3> 00384 OutputIterator1 prs_subresultants_with_cofactors 00385 (typename Polynomial_traits_d::Polynomial_d P, 00386 typename Polynomial_traits_d::Polynomial_d Q, 00387 OutputIterator1 sres_out, 00388 OutputIterator2 coP_out, 00389 OutputIterator3 coQ_out) { 00390 00391 typedef typename Polynomial_traits_d::Polynomial_d Polynomial; 00392 typedef typename Polynomial_traits_d::Coefficient_type NT; 00393 typename Polynomial_traits_d::Leading_coefficient lcoeff; 00394 typename Polynomial_traits_d::Degree degree; 00395 typename Polynomial_traits_d::Construct_polynomial construct; 00396 00397 if(degree(P) < 1 || degree(Q) < 1) { 00398 *sres_out++ = CGAL::CGALi::resultant_for_constant_polynomial 00399 <Polynomial_traits_d> (P,Q); 00400 *coP_out++ = lcoeff(Q); 00401 *coQ_out++ = lcoeff(P); 00402 return sres_out; 00403 } 00404 00405 bool poly_swapped = (degree(P) < degree(Q)); 00406 00407 if(poly_swapped) { 00408 std::swap(P,Q); 00409 } 00410 00411 Polynomial zero_pol = construct(NT(0)); 00412 std::vector<Polynomial> sres, coP, coQ; 00413 00414 int deg_diff=degree(P)-degree(Q); 00415 00416 if(deg_diff==0) { 00417 sres.push_back(Q); 00418 } else { 00419 sres.push_back(CGAL::ipower(lcoeff(Q),deg_diff-1)*Q); 00420 } 00421 00422 00423 Polynomial A,B,C,D,Quo, coPA, coPB, coQA, coQB, coPC, coQC; 00424 NT s,m; 00425 int delta,d,e; 00426 00427 coPA = construct(NT(0)); 00428 coQA = construct(CGAL::ipower(lcoeff(Q),deg_diff-1)); 00429 00430 coP.push_back(coPA); 00431 coQ.push_back(coQA); 00432 00433 A=Q; 00434 00435 s=CGAL::ipower(lcoeff(Q),deg_diff); 00436 00437 typename Polynomial_traits_d::Pseudo_division() (P, -Q, Quo, B, m); 00438 00439 coPB = construct(m); 00440 coQB = Quo; 00441 00442 00443 while(true) { 00444 d=degree(A); 00445 e=degree(B); 00446 if(B.is_zero()) { 00447 for(int i=0;i<d;i++) { 00448 sres.push_back(zero_pol); 00449 coP.push_back(zero_pol); 00450 coQ.push_back(zero_pol); 00451 } 00452 break; 00453 } 00454 00455 sres.push_back(B); 00456 coP.push_back(coPB); 00457 coQ.push_back(coQB); 00458 00459 delta=d-e; 00460 if(delta>1) { 00461 C=CGAL::ipower(lcoeff(B),delta-1)*B / CGAL::ipower(s,delta-1); 00462 00463 coPC = CGAL::ipower(lcoeff(B),delta-1)*coPB / 00464 CGAL::ipower(s,delta-1); 00465 coQC = CGAL::ipower(lcoeff(B),delta-1)*coQB / 00466 CGAL::ipower(s,delta-1); 00467 for(int i=0;i<delta-2;i++) { 00468 sres.push_back(zero_pol); 00469 coP.push_back(zero_pol); 00470 coQ.push_back(zero_pol); 00471 } 00472 sres.push_back(C); 00473 coP.push_back(coPC); 00474 coQ.push_back(coQC); 00475 00476 } 00477 else { 00478 C=B; 00479 coPC = coPB; 00480 coQC = coQB; 00481 } 00482 if(e==0) { 00483 break; 00484 } 00485 NT denominator = CGAL::ipower(s,delta)*lcoeff(A); 00486 typename Polynomial_traits_d::Pseudo_division() (A, -B, Quo, D, m); 00487 coPB = (m*coPA + Quo*coPB) / denominator; 00488 coQB = (m*coQA + Quo*coQB) / denominator; 00489 B = D / denominator; 00490 A = C; 00491 coPA = coPC; 00492 coQA = coQC; 00493 s = lcoeff(A); 00494 } 00495 00496 CGAL_assertion(static_cast<int>(sres.size()) 00497 == degree(Q)+1); 00498 00499 // If P and Q were swapped, correct the signs 00500 if(poly_swapped) { 00501 int p = degree(P); 00502 int q = degree(Q); 00503 for(int i=0;i<=q;i++) { 00504 if((p-i)*(q-i) % 2 == 1) { 00505 sres[q-i] = -sres[q-i]; 00506 coP[q-i] = -coP[q-i]; 00507 coQ[q-i] = -coQ[q-i]; 00508 } 00509 } 00510 for(int i=0;i<=q;i++) { 00511 // Swap coP and coQ: 00512 Polynomial help = coP[i]; 00513 coP[i] = coQ[i]; 00514 coQ[i] = help; 00515 } 00516 } 00517 00518 // Now, reverse the entries 00519 std::copy(coP.rbegin(),coP.rend(),coP_out); 00520 std::copy(coQ.rbegin(),coQ.rend(),coQ_out); 00521 return std::copy(sres.rbegin(),sres.rend(),sres_out); 00522 00523 } 00524 00525 // the general function for CGAL::Integral_domain_without_division_tag 00526 template <typename Polynomial_traits_d,typename OutputIterator> inline 00527 OutputIterator 00528 polynomial_subresultants_(typename Polynomial_traits_d::Polynomial_d A, 00529 typename Polynomial_traits_d::Polynomial_d B, 00530 OutputIterator out, 00531 CGAL::Integral_domain_without_division_tag){ 00532 00533 return bezout_polynomial_subresultants<Polynomial_traits_d>(A,B,out); 00534 00535 } 00536 00537 00538 // the specialization for CGAL::Integral_domain_tag 00539 template <typename Polynomial_traits_d,typename OutputIterator> inline 00540 OutputIterator 00541 polynomial_subresultants_(typename Polynomial_traits_d::Polynomial_d A, 00542 typename Polynomial_traits_d::Polynomial_d B, 00543 OutputIterator out, 00544 CGAL::Integral_domain_tag){ 00545 00546 return prs_polynomial_subresultants<Polynomial_traits_d>(A,B,out); 00547 00548 } 00549 00550 template <typename Polynomial_traits_d,typename OutputIterator> inline 00551 OutputIterator polynomial_subresultants_ 00552 (typename Polynomial_traits_d::Polynomial_d A, 00553 typename Polynomial_traits_d::Polynomial_d B, 00554 OutputIterator out) { 00555 00556 typedef typename Polynomial_traits_d::Coefficient_type NT; 00557 00558 typedef typename 00559 CGAL::Algebraic_structure_traits<NT>::Algebraic_category 00560 Algebraic_category; 00561 return polynomial_subresultants_<Polynomial_traits_d> 00562 (A,B,out,Algebraic_category()); 00563 } 00564 00565 // the general function for CGAL::Integral_domain_without_division_tag 00566 template <typename Polynomial_traits_d,typename OutputIterator> inline 00567 OutputIterator 00568 principal_subresultants_(typename Polynomial_traits_d::Polynomial_d A, 00569 typename Polynomial_traits_d::Polynomial_d B, 00570 OutputIterator out, 00571 CGAL::Integral_domain_without_division_tag){ 00572 00573 return bezout_principal_subresultants<Polynomial_traits_d>(A,B,out); 00574 00575 } 00576 00577 // the specialization for CGAL::Integral_domain_tag 00578 template <typename Polynomial_traits_d,typename OutputIterator> inline 00579 OutputIterator 00580 principal_subresultants_(typename Polynomial_traits_d::Polynomial_d A, 00581 typename Polynomial_traits_d::Polynomial_d B, 00582 OutputIterator out, 00583 CGAL::Integral_domain_tag){ 00584 00585 return prs_principal_subresultants<Polynomial_traits_d>(A,B,out); 00586 00587 } 00588 00589 template <typename Polynomial_traits_d,typename OutputIterator> inline 00590 OutputIterator principal_subresultants_ 00591 (typename Polynomial_traits_d::Polynomial_d A, 00592 typename Polynomial_traits_d::Polynomial_d B, 00593 OutputIterator out) { 00594 00595 typedef typename Polynomial_traits_d::Coefficient_type NT; 00596 00597 typedef typename 00598 CGAL::Algebraic_structure_traits<NT>::Algebraic_category 00599 Algebraic_category; 00600 return principal_subresultants_<Polynomial_traits_d> 00601 (A,B,out,Algebraic_category()); 00602 } 00603 00604 template<typename Polynomial_traits_d, 00605 typename OutputIterator1, 00606 typename OutputIterator2, 00607 typename OutputIterator3> 00608 OutputIterator1 polynomial_subresultants_with_cofactors_ 00609 (typename Polynomial_traits_d::Polynomial_d P, 00610 typename Polynomial_traits_d::Polynomial_d Q, 00611 OutputIterator1 sres_out, 00612 OutputIterator2 coP_out, 00613 OutputIterator3 coQ_out, 00614 CGAL::Integral_domain_tag) { 00615 return prs_subresultants_with_cofactors<Polynomial_traits_d> 00616 (P,Q,sres_out,coP_out,coQ_out); 00617 } 00618 00619 template<typename Polynomial_traits_d, 00620 typename OutputIterator1, 00621 typename OutputIterator2, 00622 typename OutputIterator3> 00623 OutputIterator1 polynomial_subresultants_with_cofactors_ 00624 (typename Polynomial_traits_d::Polynomial_d P, 00625 typename Polynomial_traits_d::Polynomial_d Q, 00626 OutputIterator1 sres_out, 00627 OutputIterator2 coP_out, 00628 OutputIterator3 coQ_out, 00629 CGAL::Integral_domain_without_division_tag) { 00630 // polynomial_subresultants_with_cofactors requires 00631 // a model of IntegralDomain as coefficient type; 00632 BOOST_STATIC_ASSERT(sizeof(Polynomial_traits_d)==0); 00633 return sres_out; 00634 } 00635 00636 template<typename Polynomial_traits_d, 00637 typename OutputIterator1, 00638 typename OutputIterator2, 00639 typename OutputIterator3> 00640 OutputIterator1 polynomial_subresultants_with_cofactors_ 00641 (typename Polynomial_traits_d::Polynomial_d P, 00642 typename Polynomial_traits_d::Polynomial_d Q, 00643 OutputIterator1 sres_out, 00644 OutputIterator2 coP_out, 00645 OutputIterator3 coQ_out) { 00646 00647 typedef typename Polynomial_traits_d::Coefficient_type NT; 00648 00649 typedef typename 00650 CGAL::Algebraic_structure_traits<NT>::Algebraic_category 00651 Algebraic_category; 00652 return polynomial_subresultants_with_cofactors_<Polynomial_traits_d> 00653 (P,Q,sres_out,coP_out,coQ_out,Algebraic_category()); 00654 } 00655 00671 template <typename Polynomial_traits_d,typename OutputIterator> inline 00672 OutputIterator polynomial_subresultants 00673 (typename Polynomial_traits_d::Polynomial_d p, 00674 typename Polynomial_traits_d::Polynomial_d q, 00675 OutputIterator out) { 00676 return CGAL::CGALi::polynomial_subresultants_<Polynomial_traits_d> 00677 (p, q, out); 00678 } 00679 00694 template <typename Polynomial_traits_d,typename OutputIterator> inline 00695 OutputIterator principal_subresultants 00696 (typename Polynomial_traits_d::Polynomial_d p, 00697 typename Polynomial_traits_d::Polynomial_d q, 00698 OutputIterator out) { 00699 return CGAL::CGALi::principal_subresultants_<Polynomial_traits_d> 00700 (p, q, out); 00701 } 00702 00703 template<typename Polynomial_traits_d, 00704 typename OutputIterator1, 00705 typename OutputIterator2, 00706 typename OutputIterator3> 00707 OutputIterator1 polynomial_subresultants_with_cofactors 00708 (typename Polynomial_traits_d::Polynomial_d p, 00709 typename Polynomial_traits_d::Polynomial_d q, 00710 OutputIterator1 sres_out, 00711 OutputIterator2 coP_out, 00712 OutputIterator3 coQ_out) { 00713 return CGAL::CGALi::polynomial_subresultants_with_cofactors_ 00714 <Polynomial_traits_d> (p,q,sres_out,coP_out,coQ_out); 00715 } 00716 00717 } // namespace CGALi 00718 00719 CGAL_END_NAMESPACE 00720 00721 #endif// CGAL_POLYNOMIAL_SUBRESULTANTS_H
1.7.6.1
