> <\body> <\doc-data| for algebraic systems>|> \; <|doc-data|<\doc-author-data|> \; <|doc-author-data> \; Laboratoire de Mathématiques Université de Versailles St-Quentin-en-Yvelines - France >> \; <|doc-data|>|<\author-address> Laboratoire d'Informatique \ École Polytechnique Palaiseau - France >> \; Joint Lab Meeting Waterloo, Ontario, Canada \; March 9, 2012 \; \; \; \; |<\doc-note> > |<\hidden> <\tit> Two paradigms \; <\indent> <\itemize-dot> Newton operator Relaxed algorithms \; <\indent> <\itemize-dot> ||||, '02 '09 '11]>>||, '11]>>||, '12]>>>>> |||||>||, '02 '03 '11]>>||, '12]>>>>> \; \; \ <\indent> <\itemize-dot> |||>|]>>>>> ||| (in progress)>|, ISSAC Poster '11]>>>>> |<\hidden> \; \; <\enumerate-numeric> Newton iteration for Hensel lifting \; Relaxed algorithms <\enumerate-roman> Relaxed multiplication Recursive power series Relaxed Hensel lifting\ <\itemize-minus> univariate polynomials linear systems multivariate algebraic systems |<\hidden> Let be a field. Let =,\,P|)>\k,\,Y|]>=k|]>> be an algebraic system. Let =,\,\|)>\k> be one of its zeros. \; <\question*> Can we lift \k> to a zero in |]>> ? \; <\answer> <\indent> If the Jacobian matrix >|)>\\r>> is invertible then YES. \; Throughout this talk : >|)>\0> |<\hidden> \; [ '76] <\equation*> \\\-Jac>|)>\\|)>\k>. \; <\indent> <\itemize-dot> Evaluation of |)>> Evaluation of >|)>> Invertion of |)>> Matrix-vector multiplication >|)>\\|)>> \; > What is the cost of the evaluations ? |<\hidden> Evaluate the cost of an evaluation of >. \; <\definition*> A (s.l.p.) is an ordered sequence of operations (+ conditions). \; =*Y-1,3*X|)>>:> |||||>>|=X,i=Y>>>|\i\i>>|>>>|\c\i>>|*Y>>>|\c-1>>|\X*Y-1>>>|\3*c>>|\3*X>>>>>> \; \; <\indent> <\itemize-dot> If > P\d> then |)>> (Hörner scheme). \; \; |<\hidden> <\indent> <\itemize-dot> >: polynomial multiplication in degree >|)>>: matrix multiplication in > \\-Jac>|)>\\|)>\k>> \; Suppose > is given by an with operations. We want to lift > to precision . \; <\indent> <\itemize-dot> ||||)>>>|>>>>>> |||>|)>> [ '83]>|*>>>>>> |||>|)>>>|>|)>*>>>>>> |||>|)>\\|)>>>|*>>>>>> \; \>|)>*|)>>>> \; |<\hidden> \; \; <\theorem*> '11], [, '12] > Let =,\,\|)>\k> be a zero of an algebraic system =,\,P|)>\k,\,Y|]>> such that >|)>> is invertible. Suppose > is given by an with multiplications. Then we can lift the zero > in |]>> to precision in time <\equation*> \|)>**log+>|)>|)>. \; \; >|)>*|)>> \; |<\hidden> \; \; <\enumerate-numeric> \; Relaxed algorithms <\enumerate-roman> Relaxed multiplication Recursive power series Relaxed Hensel lifting\ <\itemize-minus> univariate polynomials linear systems multivariate algebraic systems |<\hidden> Write the power series \> a*z>. \; <\itemize-dot> representation: The precision is fixed in advance. Computations in >. representation:\ <\itemize-minus> Provides a function > to increment the precision Should require the minimum knowledge on the input. \; <\itemize-dot> Addition : +b>; }> Multiplication b>: a*b>; }> \; |<\hidden> ||||||||gr-frame|>|gr-geometry||gr-color|dark magenta|magnify|0.75|gr-grid||gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||gr-edit-grid-old||1>|gr-arrow-end|\||||||||||||||||||||||||||||||>>||||||||||||||||||||||>>||||||||||||||>>|||||>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>||color|dark magenta||>>||color|dark magenta||>>|>>|>>||>>||>>||>>||>>||>>||>>>>|Naive multiplication>>|:>|*b>>>||:>|*b+a*b>>>||:>|*b+a*b+a*b>>>||:>|*b+a*b+a*b+a*b>>>||:>|*b+a*b+a*b+a*b+a*b>>>||:>|*b+a*b+a*b+a*b+a*b+a*b>>>||:>|*b+a*b+a*b+a*b>+a*b+a*b+a*b>>>|||>>>> \; \; > power series can be multiplied up to precision intime |)>>. \; >power series can be multiplied up to precision in time>. \; <\indent> > Relaxed multiplication (a.k.a. online product). |<\hidden> b> - step 0> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-arrow-end|\||||>>|||>>|||>>||>||>||>||>||>||>|>||>||>|>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-arrow-end|\||||>>|||>>|||>>||>||>||>||>|||>||>||>||>|>>>|>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|green||||>>|>>>|What we compute>>|:>|*b>>>|||>|||>|||>>|||>|||>|||>|||>|||>|||>>>> \; |<\hidden> b> - step 1> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-arrow-end|\||||>>|>||||>>||||>>|||>>|||>>|>|>||>||>||>||>||>||>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-arrow-end|\||||>>|>||||||>>|||>>|||>>|>|>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>>>|What we compute>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>|||>|||>>|||>|||>|||>|||>|||>|||>>>> \; |<\hidden> b> - step 2> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|light grey||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|light grey||||>>|>||||>>||||>>|>|>||||||||>>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|green||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>>>|What we compute>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|)>>>>|||>>|||>|||>|||>|||>|||>|||>>>> \; |<\hidden> b> - step 3> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|light grey||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>||||>>||||>>|>|>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|light grey||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>||||||>>|>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>>>|What we compute>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>|||>|||>|||>|||>|||>|||>>>> \; |<\hidden> b> - step 4> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|light grey||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|light grey||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||||||||>>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>>>|What we compute>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>||:>|z**b+a*b|\>++a*z|)>*+b*z|)>>>>|||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++a*z|)>*+b*z|)>|)>>>>|||>|||>|||>|||>>>> \; |<\hidden> b> - step 5> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>||||>>||||>>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>||||||||>>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>||||>>||||>>|>|>>>|What we compute>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>||:>|z**b+a*b|\>++a*z|)>*+b*z|)>>>>|||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>|||>|||>|||>>>> \; |<\hidden> b> - step 6> |gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>||||>>>>|What we must compute>>||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|white||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>||||>>||||>>|>|>||||||||||||>>>>|Minimum knowledge on the input>>>>>> |||||||||gr-frame|>|gr-geometry||gr-grid||1>|gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||1>|gr-edit-grid-old||1>|gr-grid-aspect-props|||>|gr-grid-aspect||>|magnify|0.75|gr-fill-color|green||||>>|>||||>>||||>>|>|>||||>>||||>>||||>>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>|>|>|>|>||||>>||||>>|>|>||||>>||||>>||||>>||||>>||||>>|>|>|>|>|>>>|What we compute>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>||:>|z**b+a*b|\>++a*z|)>*+b*z|)>>>>|||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|\>>>>||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++a*z|)>*+b*z|)>>>>|||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++\+a*z|)>*+\+b*z|)>|)>>>>>>> \; |<\hidden> \; <\theorem*> , '74], [, '97], ['97]> Let and be two power series known up to precision, then,\,> can be computed in time <\equation*> =\*log N|)>. \; \; ||||||gr-frame|>|gr-geometry||gr-fill-color|green|gr-color|dark magenta|magnify|0.75|gr-grid||gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||gr-edit-grid-old||1>|||||||||||||||||||||||||||||||||||>>|||||||||||||||>>||>>|||||>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>|>>>>|Relaxed multiplication>>|:>|*b>>>||:>|z* \ \ \ *b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>||:>|z**b+a*b|\>++a*z|)>*+b*z|)>>>>|||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++a*z|)>*+b*z|)>|)>>>>||:>|z**b+a*b|)>>>>||:>|z**b+a*b++a*z|)>*+b*z|)>|\>>>>||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++a*z|)>*+b*z|)>>>>|||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++\+a*z|)>*+\+b*z|)>|)>>>>>>> |<\hidden> \; \; <\enumerate-numeric> \; <\enumerate-roman> Recursive power series Relaxed Hensel lifting\ <\itemize-minus> univariate polynomials linear systems multivariate algebraic systems |<\hidden> power series> <\definition*> Apower series is if\ <\indent> <\itemize-dot> > =|)> \ \> only depends on,\,y> <\example*> Ifk|]>> are such that\0>, thena/b\k|]>> is recursive. <\equation*> c=|)>*c|b>,c=a/b . |<\hidden> <\equation*> c=|z>|)>*c|)>|b>,c=a/b. > \; |<\hidden> power series> <\definition*> Apower series is if\ <\indent> <\itemize-dot> > =|)> \ \ \> only depends on,\,y> <\example*> Ifk|]>> are such that\0>, thenk|]>> is recursive.\ <\equation*> \|z>|)>=b+b*z+\ ,d\*c,c=>,c=a/b. \; |||||:>|*c>>| d>>| c=-d|)>/b>>>||||>||||>||||>||||>||||>>>> |<\hidden> ||||||||:>|*c>>| d>>| c=-d|)>/b>>>|:>|z* \ \ \ *c+b*c|)>>>| d>>| c=-d|)>/b>>>||||>||||>||||>||||>>>> |<\hidden> |||||||||||:>|*c>>| d>>| c=-d|)>/b>>>|:>|z* \ \ \ *c+b*c|)>>>| d>>| c=-d|)>/b>>>|:>|z**c+b*c++b*z|)>*+c*z|)>|)>>>| d>>| c=-d|)>/b>>>||||>||||>||||>>>> |<\hidden> ||||||||||||||:>|*c>>| d>>| c=-d|)>/b>>>|:>|z* \ \ \ *c+b*c|)>>>| d>>| c=-d|)>/b>>>|:>|z**c+b*c++b*z|)>*+c*z|)>|)>>>| d>>| c=-d|)>/b>>>|:>|z**c+b*c|)>>>| d>>| c=-d|)>/b>>>||||>||||>>>> |<\hidden> ||||||||||||||:>|*c>>| d>>| c=-d|)>/b>>>|:>|z* \ \ \ *c+b*c|)>>>| d>>| c=-d|)>/b>>>|:>|z**c+b*c++b*z|)>*+c*z|)>|)>>>| d>>| c=-d|)>/b>>>|:>|z**c+b*c|)>>>| d>>| c=-d|)>/b>>>|:>|z**c+b*c|\>++b*z|)>*+c*z|)>>>| d>>| c=-d|)>/b>>>||| \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ++b*z|)>*+c*z|)>|)>>>||>>>> \; Relaxed division in time:> \ +\> > |<\hidden> <\definition*> \; <\indent> <\itemize-dot> An operator > is if > only depends on,\,y>. A recursive operator > is a is the shift is explicit. \; <\example*> |||||>>|>>>|=|)>*y|b>>, \ =a/b>>|=|z>|)>*y|)>|b>>>>||>|=y+z>, \ =0>>|=z*|)>+z>>>>>> \; <\proposition*> Let\k|]>> be given by a s.l.p. with multiplications. Let k|]>> such that >.Then can be computed at precision in time +\>. |<\hidden> \; <\enumerate-numeric> <\enumerate-roman> Relaxed Hensel lifting\ <\itemize-minus> univariate polynomials linear systems multivariate algebraic systems \; <\indent> <\itemize-dot> Transform an implicit polynomial equation into a recursive equation (with explicit shift) <\equation*> \|)>=\ \ \ \ \ \ \ \ \ \ \=\|)> |<\hidden> \; Letk|]>> and let> be a simple root of modulo. \; \ There exists a unique k|]>> such that +\> and=0>. \; \; ||>>|>||)>+P|)>|)>+|)>*Q>>>||||>||>>|>||)>*y+|)>-P|)>*y+|)>*Q|)>|\> involves only y,\,y>>>>>||||>||||>||>|>||)>-P|)>*y+|)>*Q|-P|)>>>>>>>||||>>>> |<\hidden> ||>>|>||)>+P|)>|)>+|)>*Q>>>||||>||>>|>||)>*y+|)>-P|)>*y+|)>*Q|)>|\> involves only y,\,y>>>>>||||>||||>||>|>||)>-P|)>*y+z*|z>|)>*Q|)>|-P|)>>>>>>||||>>>> > \; |<\hidden> |]>>> <\theorem*> '12]> Letk|]>> and > be a simple root of modulo. Let k|]>> be the unique lifted root from >. Then one can compute at precision in time <\equation*> d*+\ where. \; <\proof> Compute the fixed point of the recursive equation: <\equation*> y=\\|)>-P|)>*y+z*|z>|)>*Q|)>|-P|)>> \; \ *+\> |<\hidden> |]>>> Recall that the lifted root k|]>> of satisfies <\equation*> y=\\|)>-P|)>*y+z*|z>|)>*Q|)>|-P|)>> \; <\theorem*> '12]> <\itemize-dot> If is given as an s.l.p. with > multiplications then there exists a s.l.p. with multiplications that computes \>. The lifted rootk|]>> of can be computed at precision in time*+\>. \; \ |)>*+\> |<\hidden> \; \; <\enumerate-numeric> \; <\enumerate-roman> <\itemize-minus> linear systems multivariate algebraic systems (dense / s.l.p.) \; |<\hidden> \; Let \|]>|)>>, \|]>|)>>. Find \|]>|)>> such that <\equation*> A*\X=B. \; >*\|)>> \; <\indent> <\itemize-dot> Compute *A\\|]>> by <\equation*> C=B\|z>\C|)>|)>,C=B*A . \; Cost: *|)>> \; Similar to a divide-and-conquer approach \; \; \; |<\hidden> \; For such thatj\k\r>, let >\\|]>|)>> such that <\equation*> \|)>=\|)>+\*\|)>-\|)>+j\k\r>\>|)>*-y|)>*-y|)>. \; Evaluate > to the lifted zero > <\equation*> \=\|)>=\*\|)>\\+|)>-\*\|)>\\+j\k\r>\>|)>*-y|)>*-y|)>|)>|\> involves only \,\,\>>. \; \; Recursive equation: <\equation*> \=-\*\|)>\|)>-\*\|)>\\+j\k\r>\>|)>*-y|)>*-y|)>|)>. |<\hidden> Recursive equation (with explicit shift) : <\equation*> \=-\*\|)>\|)>-\*\|)>\\+z*j\k\r>\>|)>*-y|z>|)>*-y|z>|)>|)>|)>. > |<\hidden> \; \; <\theorem*> '12]> Let> be an algebraic system in|]>|]>>, where=,\,Y|)>> and let> be a regular root of> modulo. Suppose > \\d>. Let \k|]>> be the unique lifted root from >.\ Then one can compute> at precision in time <\equation*> \+r|)>*+*d+r>|)>|)> where>. \; \; *d+r>|)>*|)>> |<\hidden> \; <\theorem*> '12]> <\itemize-dot> If > is given as an s.l.p. with multiplications then there exists a s.l.p. with |2>> multiplications that computes \\|)>>. We can lift the root\k|]>> of> at precision in time <\equation*> |)>*+>|)>|)>>. \; \; \ >|)>*|)>> |<\hidden> <\with|font-base-size|14> <\tit> Conclusion \; |||||||>||>||>||>||>||>||>>>> \; \; , (in progress)\ \; \ <\indent> <\itemize-dot> Relaxed linear algebra for structured or sparse matrices Relaxed lifting of triangular sets \; |<\hidden> \; \; \; \; <\with|par-mode|center> \; \; <\granite> <\with|font-base-size|20> Thank you for your attention! > <\initial> <\collection> <\references> <\collection> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> |\>|?>> > <\auxiliary> <\collection> <\associate|figure> > > > > > > > > > > > > > > > > > > > > > > >