Newton-Hensel interpolation lifting
The main result of this paper is a new version of Newton-Hensel lifting that relates to interpolation questions. It allows one to lift polynomials in ℤ[x] from information modulo a prime number p ≠ 2 to a power p k for any k, and its originality is that it is a mixed version that not only lifts the...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 09099caa a22009137a 4500 | ||
|---|---|---|---|
| 001 | PAPER-7328 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203704.0 | ||
| 008 | 190411s2006 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-31944448714 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Avendaño, M. | |
| 245 | 1 | 0 | |a Newton-Hensel interpolation lifting |
| 260 | |c 2006 | ||
| 270 | 1 | 0 | |m Avendaño, M.; Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Pabellón i Ciudad Universitaria, 1428 Buenos Aires, Argentina; email: mavendar@bigua.dm.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Apostol, T., (1976) Introduction to Analytic Number Theory, , Undergraduate Texts in Mathematics, Springer-Verlag, New York | ||
| 504 | |a Ben-Or, M., Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation. Extended abstract (1988) STOC, pp. 301-309 | ||
| 504 | |a Bürgisser, P., Clausen, M., Shokrollahi, M., (1997) Algebraic Complexity Theory, 317. , Springer | ||
| 504 | |a Blum, L., Dicker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , Springer-Verlag, New York | ||
| 504 | |a Borodin, A., Tiwari, P., On the decidability of sparse univariate polynomial interpolation (1991) Comput. Complexity, 1, pp. 67-90 | ||
| 504 | |a (1988) STOC, pp. 301-309 | ||
| 504 | |a Carmichael, R., (1959) The Theory of Numbers, , Copyright 1914 and 1915 by R. Carmichael, Dover, New York | ||
| 504 | |a Chistov, A., Factoring polynomials over a finite field and solution of systems of algebraic equations (Russian. English summary.) Theory of the complexity of computations, II (1984) Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 137, pp. 124-188 | ||
| 504 | |a Chistov, A., Grigoriev, D., (1982) Polynomial Time Factoring of the Multivariate Polynomials over a Global Field, 39p. , Preprint LOMI E-5-82 | ||
| 504 | |a Chistov, A., Grigoriev, D., (1983) Subexponential-time Solving Systems of Algebraic Equations I, II, 119p. , Preprint LOMIE-9-83, E-10-83 | ||
| 504 | |a Clausen, M., Dress, A., Grabmeier, J., Karpinski, M., On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields (1991) Theoret. Comput. Sci., 84, pp. 151-164 | ||
| 504 | |a Cucker, F., Smale, S., Complexity estimates depending on condition and round-off error (1999) J.A.C.M., 46, pp. 113-184 | ||
| 504 | |a Dedieu, J.-P., Shub, M., Newton's method for overdetermined systems of equations (2000) Math. Comp., 69, pp. 1099-1115 | ||
| 504 | |a Dress, A., Grabmeier, J., The interpolation problem for k-sparse polynomials and character sums (1991) Adv. in Appl. Math., 12, pp. 57-75 | ||
| 504 | |a Esmonde, J., Murty, M.R., (1999) Problems in Algebraic Number Theory, 190. , Graduate Texts in Mathematics, Springer-Verlag, New York | ||
| 504 | |a Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Pardo, L.M., Lower bounds for diophantine approximations (1997) J. Pure AppL Algebra, 117-118, pp. 277-317 | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure AppL Algebra, 124, pp. 101-146 | ||
| 504 | |a Grigoriev, D., Factoring polynomials over a finite field and solution of systems of algebraic equations (Russian. English summary.) Theory of the complexity of computations, II (1984) Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 137, pp. 20-79 | ||
| 504 | |a Grigoriev, D., Karpinski, M., Singer, M., Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields (1990) SIAM J. Comput., 19 (6), pp. 1059-1063 | ||
| 504 | |a Grigoriev, D., Karpinski, M., Singer, M., The interpolation problem for k-sparse sums of eigenfunctions of operators (1991) Adv. in Appl. Math., 12, pp. 76-81 | ||
| 504 | |a Grigoriev, D., Karpinski, M., Singer, M., Computational complexity of sparse rational function interpolation (1995) SIAM J. Comput., 23, pp. 1-11 | ||
| 504 | |a Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16, pp. 70-109 | ||
| 504 | |a Jeronimo, G., Krick, T., Sabia, J., Sombra, M., The computational complexity of the Chow form (2004) Found. Comput. Math., 4, pp. 41-117 | ||
| 504 | |a Kaltofen, E., Polynomial-time reductions from multivariate to bi- And univariate integral polynomial factorization (1985) SIAM J. Comput., 14 (2), pp. 469-489 | ||
| 504 | |a Kaltofen, E., Lakshman, Y.N., Improved sparse multivariate polynomial interpolation algorithms, ISSAC'88 (1988) Proc. 1988 Internat. Symp. Symbolic Algebraic Comput., 358, pp. 467-474. , Lecture Notes in Comput. Sci. Springer-Verlag, New York | ||
| 504 | |a Kaltofen, E., Lakshman, Y.N., Wiley, J.-M., Modular rational sparse multivariate polynomial interpolation, ISSAC'90 (1990) Proc. 1990 Internat. Symp. Symbolic Algebraic Comput., pp. 135-139. , S. Watanabe and M. Nagata, eds., ACM Press, New York | ||
| 504 | |a Kaltofen, E., Lee, W.-S., Early termination in sparse interpolation algorithms (2003) J. Symbolic Comput., 40 | ||
| 504 | |a Kaltofen, E., Lobo, A., Lee, W.-S., Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm (2000) ISSAC'00, Proc. 2000 Internat. Symp. Symbolic Algebraic Comput., pp. 192-201. , C. Travero, ed., ACM Press, New York | ||
| 504 | |a Lecerf, G., Quadratic Newton iteration for systems with multiplicity (2002) Found. Comput. Math., 2, pp. 247-293 | ||
| 504 | |a Lee, W.-S., (2001) Early Termination Strategies in Sparse Interpolation Algorithms, , Ph.D. Dissertation, North Carolina State University | ||
| 504 | |a Lenstra, A.K., Lenstra, H.W., Lovász, L., Factoring polynomials with rational coefficients (1982) Math. Ann., 261, pp. 515-534 | ||
| 504 | |a (2004) PARI/GP, Version 2. 2. 8, , http://pari.math.u-bordeaux.fr/, Webpage | ||
| 504 | |a Serre, J.-P., (1970) Cours D'Arith' Métique, , Presses Universitaires de France | ||
| 504 | |a Shub, M., Smale, S., Complexity of Bezout's theorem V: Polynomial time (1994) Theoret. Comp. Sci., 133, pp. 141-164 | ||
| 504 | |a Smale, S., Newton's method estimates from data at one point (1986) The Merging of Disciplines: New Directions in Pure, Applied and Computational Mathematics, , R. Erwing, K. Gross, and C. Martin, eds.. Springer-Verlag, New York | ||
| 504 | |a Smale, S., Mathematical problems for the next century (1998) Math. Intelligencer, 20, pp. 7-15 | ||
| 504 | |a Trinks, W., On improving approximate results of buchberger's algorithm by Newton's method (1985) Lecture Notes in Computer Science, 204, pp. 608-611. , Springer-Verlag, New York | ||
| 504 | |a Winkler, F., A p-adic approach to the computation of Gröbner bases (1988) J. Symbolic Comput, 6, pp. 287-304 | ||
| 504 | |a Zassenhaus, H., On Hensel factorization I (1969) J. Number Theory, 1, pp. 291-311 | ||
| 504 | |a Zippel, R., Interpolating polynomials from their values (1990) J. Symbolic Comput., 9, pp. 375-403 | ||
| 520 | 3 | |a The main result of this paper is a new version of Newton-Hensel lifting that relates to interpolation questions. It allows one to lift polynomials in ℤ[x] from information modulo a prime number p ≠ 2 to a power p k for any k, and its originality is that it is a mixed version that not only lifts the coefficients of the polynomial but also its exponents. We show that this result corresponds exactly to a Newton - Hensel lifting of a system of 2t generalized equations in 2t unknowns in the ring of p-adic integers ℤp. Finally, we apply our results to sparse polynomial interpolation in ℤ[x]. © 2005 SFoCM. |l eng | |
| 593 | |a Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Pabellón i Ciudad Universitaria, 1428 Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a NEWTON-HENSEL LIFTING |
| 690 | 1 | 0 | |a P-ADIC INTEGERS |
| 690 | 1 | 0 | |a SPARSE POLYNOMIAL INTERPOLATION |
| 690 | 1 | 0 | |a GENERALIZED EQUATIONS |
| 690 | 1 | 0 | |a HENSEL LIFTING |
| 690 | 1 | 0 | |a NEWTON-HENSEL LIFTING |
| 690 | 1 | 0 | |a P-ADIC INTEGERS |
| 690 | 1 | 0 | |a PRIME NUMBER |
| 690 | 1 | 0 | |a SPARSE POLYNOMIAL INTERPOLATIONS |
| 690 | 1 | 0 | |a COMPUTATIONAL METHODS |
| 690 | 1 | 0 | |a INTERPOLATION |
| 700 | 1 | |a Krick, T. | |
| 700 | 1 | |a Pacetti, A. | |
| 773 | 0 | |d 2006 |g v. 6 |h pp. 81-120 |k n. 1 |p Found. Comput. Math. |x 16153375 |t Foundations of Computational Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-31944448714&doi=10.1007%2fs10208-005-0172-3&partnerID=40&md5=89d4802fb4549fee2e73c1fdb90f7240 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10208-005-0172-3 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_16153375_v6_n1_p81_Avendano |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v6_n1_p81_Avendano |y Registro en la Biblioteca Digital |
| 961 | |a paper_16153375_v6_n1_p81_Avendano |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 68281 | ||