作业5

本作业涵盖了第17到21讲的材料

截止日期:4月12日。

适用于作业5的LaTeX模板,以备您使用LaTeX编写时使用。

必修课

请记住,您只需要在以下6个练习中上交5个即可。

问题1-快速模块化组合(20分)

令g = h = x3 + 2×2 + 3x + 4和f = x4-1是F5 [x]上的多项式。使用快速模块化合成算法来计算g(h)modf。

问题2-证明ωdet=ωmult(20分)

给定一个矩阵A∈FN×N,其中N = 2k,证明人们可以在时间O(nω)中计算det(A),其中ω是矩阵乘法指数。您可以假定您需要在过程中求逆的任何矩阵都是可逆的。

可选问题:如何删除上面给出的假设?

问题3-线性递归关系和最小多项式(20分)
如果h(x)= ∑i≥0aixi是

h(x)= x2 + xx3-x-1

给定递归顺序最多为4,计算有理数序列1、3、4、7、11、18、29、47等的最小多项式。给定序列的下5个元素。
问题4-使用线性递归关系确定奇点(20分)

设A∈Qn×n为方阵。给出一个概率“黑盒”算法,该算法最多执行O(c(A)⋅n+ n2)个场运算,并确定A是否为奇数。您的算法应以至少2/3的概率返回正确的答案。

问题5-Toeplitz矩阵(20分)

Toeplitz矩阵A∈Fn×n是一个矩阵,其条目沿对角线是恒定的,例如:

A =(321432543)

证明您可以在O(M(n))运算中将n×n Toeplitz矩阵乘以n×1向量,其中回想M(n)是将两个≤n的多项式相乘所需的运算数。

证明给定β∈F,您可以在F的O(n)运算中计算β0,β1,β4,β9,…,β(n-1)2。

提示:想想(i + 1)2-i2

给定度数<n且α∈F的多项式f(x)∈F[x],现在让我们看看如何计算f(α0),f(α1),…,f(αn-1)我们知道β∈F使得β2=α(即α的平方根)。

设f(x)= f0 + f1x + … + fn-1xn-1

(f0,…,fn-1)↦(f(α0),…,f(αn-1))?

通过显示此矩阵的(i,j)项来描述此矩阵。

利用ij =(i + j)2-i2-j22的事实,将前一部分的矩阵重写为3个矩阵的乘积,涉及特定的Toepliz矩阵。

建议:先写下n = 3

证明您可以在O(M(n))运算中计算f(α0),f(α1),…,f(αn-1)。
问题6-维德曼的算法(20分)

在Maple或Macaulay2中实现Wiedemann算法(如我们在课堂上所见),以解决稀疏线性系统。作为输入,该算法将采用:

整数n(矩阵的大小),
一个质数p(我们在Fp中工作),
在0,…,p-1中的n个整数(这是右向量b)
一个三元组i,j,ai,j的序列,其中i,j∈1,…,n和ai,j∈0,…,p-1(这些是矩阵A中的非零项)。

输出是向量x,使得Ax = b。该算法是随机的,但是如果出现问题,您可以将其检测出来。在这种情况下,请返回“错误”,或引发异常或类似的事情。我们将以与上述相同的格式给出输入矩阵。您的代码应通过大小为10和100且大小为p = 9001的输入;系数模为p = 2的输入矩阵更具挑战性(算法很有可能失败)。

p = 9001的输入矩阵:大小10,大小100,大小1000,大小10000

输入矩阵p = 2(风险自负):大小50

您必须实现用于发现给定序列的递归的算法,但不必重新实现多项式乘法或除法。请记住,所有计算都必须以p为模。

实践问题

您无需针对这些问题提交解决方案,但强烈建议您为自己的知识而尝试这些问题。 🙂

问题1

让您的基本字段为F5并考虑
A =(123401131),b =(012)

使用Wiedemann算法计算A-1b。

Homework 5

This homework covers the material from lectures 17 to 21

Due date: April 12th.

LaTeX template for homework 5, in case you want to write it in LaTeX.

Required Exercises

Remember that you are only required to turn in 5 out of the 6 exercises below.

Problem 1 – Fast Modular Composition (20 points)

Let 

g=h=x3+2x2+3x+4

 and 

f=x41

 be polynomials over 

F5[x]

. Use the fast modular composition algorithm to compute 

g(h)modf

.

Problem 2 – proving that 

ωdet=ωmult

 (20 points)

Given a matrix 

AFN×N

 where 

N=2k

, prove that one can compute 

det(A)

 in time 

O(nω)

, where 

ω

 is the matrix multiplication exponent. You can assume that any matrix that you need to invert in the process is invertible.

Optional question: how would you remove the assumption given above?

Problem 3 – linear recurrence relations and minimal polynomials (20 points)

  1. Determine a recurrence relation and sufficiently many initial values of the sequence 
    (ai)iNQN

     if 

    h(x)=i0aixi

     is

h(x)=x2+xx3x1

  1. Compute the minimal polynomial of the sequence 
    1,3,4,7,11,18,29,47,

     of rational numbers, given that the recursion order is at most 4. Give the next 5 elements of the sequence.

Problem 4 – using linear recurrent relations to decide singularity (20 points)

Let 

AQn×n

 be a square matrix. Give a probabilistic “black box” algorithm which performs at most 

O(c(A)n+n2)

 field operations and decides whether 

A

 is singular. Your algorithm should return the correct answer with probability at least 

2/3

.

Problem 5 – Toeplitz matrices (20 points)

A Toeplitz matrix 

AFn×n

 is a matrix whose entries are constant along the diagonals, for instance:

A=(321432543)

  1. Prove that you can multiply an 
    n×n

     Toeplitz matrix by an 

    n×1

     vector in 

    O(M(n))

     operations, where recall that 

    M(n)

     is the number of operations needed to multiply two polynomials of degree 

    n

    .

  2. Prove that given 
    βF

    , you can compute 

    β0,β1,β4,β9,,β(n1)2

     in 

    O(n)

     operations in 

    F

    .

Hint: think of 

(i+1)2i2

  1. Given a polynomial 
    f(x)F[x]

     with degree 

    <n

    , and 

    αF

    , let us now see how to compute 

    f(α0),f(α1),,f(αn1)

    , assuming that we know 

    βF

     such that 

    β2=α

     (that is, a square root of 

    α

    ).

Let 

f(x)=f0+f1x++fn1xn1

 What is the matrix of the operation

(f0,,fn1)(f(α0),,f(αn1))?

Describe this matrix by showing what the 

(i,j)

 entry of this matrix is.

  1. Using the fact that 
    ij=(i+j)2i2j22

    , rewrite the matrix from the previous part as a product of 3 matrices, involving a particular Toepliz matrix.

Suggestion: write this down for 

n=3

 first

  1. Show that you can compute 
    f(α0),f(α1),,f(αn1)

     in 

    O(M(n))

     operations.

Problem 6 – Wiedemann’s algorithm (20 points)

Implement, in Maple or Macaulay2, the Wiedemann algorithm (as we saw in class) for solving a sparse linear system. As input, the algorithm will take:

  • an integer 
    n

     (size of the matrix),

  • a prime integer 
    p

     (we work in 

    Fp

    ),


  • n

     integers in 

    0,,p1

     (this is the right-hand vector 

    b

    )

  • a sequence of triples 
    i,j,ai,j

    , with 

    i,j1,...,n

     and 

    ai,j0,...,p1

     (these are the non-zero entries in the matrix 

    A

    ).

The output is a vector 

x

 such that 

Ax=b.

 The algorithm is randomized, but if something goes wrong, you can detect it; in this case, return “error”, or throw an exception, or something along these lines. We will give input matrices, with the same format as above. Your code should pass the inputs of size up to 

10

 and 

100

 with 

p=9001

; the input matrix with coefficients modulo p = 2 is more challenging (there is a good chance the algorithm will fail).

Input matrices for 

p=9001

: size 10, size 100, size 1000, size 10000

Input matrices for 

p=2

 (do it at your own risk): size 50

You have to implement the algorithm for discovering a recurrence for a given sequence, but you do not have to reimplement polynomial multiplication or division. Remember, all computations must be done modulo 

p

.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. 🙂

Problem 1

Let your base field be 

F5

 and consider

A=(123401131),   b=(012)

Compute 

A1b

 using Wiedemann’s algorithm.


EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue


EasyDue™是一个服务全球中国留学生的专业代写公司
专注提供稳定可靠的北美、澳洲、英国代写服务
专注提供CS、统计、金融、经济、数学等覆盖100+专业的作业代写服务