Work on a BASH Scipt to Find Polynomials Using the Best of Msieve and CADO-NFS

[chris2be8]

Glad I could help. Let me know if you want any bits I left out (eg finding out what files to sort on).

I can't test it myself because most of my PCs are shut down for the duration of the energy shortage in Europe. Including my main GPU.

[Gimarel]

Originally Posted by EdH

I already do a short run of Msieve -np1, terminate it, and read the degree (for the later conversion) and stage2_norm . I can modify it as I wish and make the multiple runs.

Currently I don't know a way how to tell unmodified msieve to output the norm of the sopt-optimized poly. And if you want to rootsieve say 1000 polys, then you have to make at least 6000 starts of msieve.

[EdH]

I got tied up with some other things and haven't done anything other than mentally going over things. Here is my present organization and plan.

I've now moved to the idea of a set of scripts:

A controlling script that will perform an initial Msieve run for 5 seconds to acquire some values from msieve.log. It will also contain user values for GPU, threads, starting coefficient and deadline, as well as other things I find useful/necessary. At that point, it will start one or more scripts to handle the -np1 and -nps across multiple threads, using command line arguments to separate coefficient ranges.

The main script will take command line arguments to include the starting range for coefficients, stage1 and stage2 norms and a deadline. It will be designed to run -np1 -nps for a limited time instead of completing a range. It will then proceed with CADO-NFS sopt and back to Msieve rootopt. This script will be able to perform everything, but will output unique files from others being run in parallel via separate invocations.

A completion script that will compare all the best polynomials and rank them, or merely present them for user review.

I think I have most of the workings ironed out, but the implementation will reveal my shortcomings.

I'm still not sure I understand the last bit about the values for the Msieve root opt, but I need to get the rest of the scripting in work and see if a light brightens.

Thanks all for the help. I may take a while with this, but I hope I can come up with something that will work for others as well as for me. Because of that view, I'm shying away from Msieve modification, at least for now.

[EdH]

Here's a progress report on where my scripts have moved to. I did a test run overnight that ran through the CADO-NFS sopt and culling steps across all 24 threads of a CPU only machine. I set it up in the following manner:

The controlling machine was set to start the process at 1M minimum coefficient and set each of the 24 threads at +.2M from the previous thread (1M, 1.2M, 1.4M, ...). It ran a preliminary -np1 for 5 seconds and harvested the degree and stage2_norm. I used a multiplier of 3 against the stage2_norm to increase -nps returns. I set a search deadline of 4 hours (14400s).

The controlling machine called 24 processes via gnome-terminal with each thread running the second script, which read the values from the controlling script for each separate process. top showed nearly a full 100% for CPU use.

This morning I reviewed the culled sets of CADO-NFS sopt polynomials and found a couple of interesting exp_E returns. Here's a list of the smallest three for each thread:

testE is 58.77 (57.48, 56.59, 56.31)
testE is 58.17 (56.86, 56.55, 56.28)
testE is 59.81 (56.84, 56.51, 56.45)
testE is 59.17 (57.34, 56.60, 55.76)
testE is 59.33 (57.48, 56.59, 56.15)
testE is 59.40 (57.07, 57.06, 56.82)
testE is 58.14 (57.19, 56.82, 56.34)
testE is 58.59 (57.53, 56.77, 56.45)
testE is 59.87 (57.24, 56.68, 56.64)
testE is 59.07 (57.02, 56.57, 54.79)
testE is 58.48 (56.80, 56.62, 56.57)
testE is 59.25 (56.43, 56.29, 55.30)
testE is 57.99 (56.85, 56.30, 56.08)
testE is 59.24 (56.49, 56.22, 56.21)
testE is 58.77 (56.74, 56.62, 56.07)
testE is 60.23 (57.05, 56.80, 56.59)
testE is 57.81 (57.34, 56.60, 56.38)
testE is 58.77 (56.69, 56.52, 55.95)
testE is 58.15 (56.14, 53.61, 53.53)
testE is 59.38 (56.56, 56.50, 55.53)
testE is 59.89 (57.06, 56.65, 56.36)
testE is 58.46 (57.43, 56.97, 56.47)
testE is 59.83 (56.65, 56.52, 56.31)
 testE is 59.07 (56.56, 56.54, 56.28)

My next step will be to learn what I need to do to run Msieve rootopt on all the better candidates.

At some point, I'll clean up and comment the two scripts and post them in case anyone else would like to play and provide feedback.

[EdH]

Here are the scripts as they currently stand, with lots of commenting within.

I am running this script in a directory in which Msieve was compiled and it is of equal directory level with the cado-nfs directory, such that ../cado-nfs/build/<etc.> can be called. I have named this directory "polyWork." The scripts are named polyFindc.sh (the controlling script) and polyFindm.sh (the worker script), They can be named alternate names, but the "gnome-terminal" call will need to be modified if the worker script is named something else.

This is the controlling script (polyFindc.sh) which runs as many of the other as provided for by threads:

#!/bin/bash
#####################################
## This script is designed to use  ##
## portions of Msieve and CADO-NFS ##
## to find polynomials. Pari/gp is ##
## also needed.                    ##
##                                 ##
## This is the controlling script  ##
## for the others that will do the ##
## actual work.                    ##
#####################################

# set path to polyWork directory:
cd $HOME/Math/polyWork

# Set values for Msieve and CADO-NFS
# operations:

# This sets the starting coefficient
# for the first machine
minc=1000000

# This sets how much to add for the
# coefficients for each added thread.
addc=200000

# This sets how many threads to use.
threads=24

# The harvested stage2_norm is multiplied
# by this value.
stage2multiplier=3

# This is used to stop all polysearch
# after this delay in seconds.
deadline=14400

# These make sure the log file is
# current so no errors are encountered
# from a previous run.
rm polyFind.log 2>/dev/null
rm polyFind.dat* 2>/dev/null

# This section allows for a new composite
# to take the place of a former one.
if [ ${#1} -gt 60 ]
  then
    composite=$1
  elif [ -e worktodo.ini ]
    then
      read composite <worktodo.ini
  else
    echo -n "Enter composite: "
    read composite in
fi
echo "$composite" >worktodo.ini

echo "Finding polynomials for: $composite"

# This run is brief and is only for data harvesting
./msieve -s polyFind.dat -l polyFind.log -np1 "min_coeff=${minc}, poly_deadline=5"
st2n=$(cat polyFind.log | grep "stage 2 norm")
st2n=${st2n:44}
echo "st2n is $st2n"
st2=$(echo "${st2n}*${stage2multiplier}" | gp -qf)
degree=$(cat polyFind.log | grep "polynomial degree:")
degree=${degree:${#degree}-1:1}

# This section invokes the second script
# across all the threads as tabs within
# the same terminal.
thread=$threads
while [ $thread -gt 0 ]
  do
    gnome-terminal --title="pF${thread}" --tab -- bash polyFindm.sh $minc $st2 $degree $thread
    let thread=${thread}-1
    let minc=${minc}+${addc}
  done
sleep $deadline
killall msieve
sleep 10
# This script will continue with sections to wait for all returns from the other threads and final processing of the best found and optimized polynomial(s).

Here is the script (polyFindm.sh) for the main poly searching and processing:

#!/bin/bash
#####################################
## This script is designed to use  ##
## portions of Msieve and CADO-NFS ##
## to find polynomials. Pari/gp is ##
## also needed.                    ##
##                                 ##
## This is the main script for the ##
## set. It can be run as a stand   ##
## alone script, or be called by   ##
## the controlling script.         ##
#####################################

# set path to polyWork directory:
cd $HOME/Math/polyWork

# Set composite for use with routine
# that converts Msieve polys to CADO-
# NFS sopt readable polys.
read composite <worktodo.ini

# Set values for Msieve and CADO-NFS
# operations. These can be entered
# if not provided via command line.
if [ ${#1} -lt 1 ]
  then
    echo -n "Enter min_coeff: "
    read minc in
  else
    minc=$1
fi
if [ ${#2} -lt 1 ]
  then
    echo -n "Enter stage2_norm: "
    read st2 in
  else
    st2=$2
fi

# This is used in the
# conversion for sopt.
if [ ${#3} -lt 1 ]
  then
    degree=6
  else
    degree=$3
fi

# This is used to keep files
# separate between threads.
if [ ${#4} -lt 1 ]
  then
    thread=0
  else
    thread=$4
fi

echo "Found $minc $st2 $degree $thread"

# This cleans up any previous files.
rm polyFind${thread}.* 2>/dev/null

# This is the main run to search for
# polys starting at the supplied
# coefficient range.  The range is
# open-ended, with a kill signal
# expected to stop the search.
./msieve -s polyFind${thread}.dat -l polyFind${thread}.log -nps -np1 "min_coeff=${minc} stage2_norm=$st2"

# This section creates a CADO-NFS
# sopt readable file.
rm polys4sopt${thread}
exec <"polyFind${thread}.dat.ms"
  while read line
    do
      line=($line)
      coeff=$degree
      index=0
      echo "n: $composite" >> polys4sopt${thread}
      while [ $coeff -gt -1 ]
        do
          echo "c${coeff}: ${line[index]}" >> polys4sopt${thread}
          let coeff=${coeff}-1
          let index=${index}+1
        done
      echo "Y1: ${line[index]}" >> polys4sopt${thread}
      let index=${index}+1
      echo "Y0: ${line[index]}" >> polys4sopt${thread}
      echo "" >> polys4sopt${thread}
    done

# This section runs sopt at two
# values (0 and 1).
for s in 0 1
  do
    ../cado-nfs/build/$HOSTNAME/polyselect/sopt -inputpolys polys4sopt${thread} -sopteffort $s -v >> soptset${thread}
  done

# This section finds the lowest three
# exp_E values from the sopt set.
lowestE1=99.99
lowestE2=99.99
lowestE3=99.99
rm culledset${thread} 2>/dev/null
exec <"soptset${thread}"
 while read line
   do
     case $line in
       "# lognorm "*) testE=$line
         E=$(echo `expr index "$testE" E`)
         testE=${testE:${E}+1:5}
#         echo "testE is $testE (${lowestE3}, ${lowestE2}, ${lowestE1})" 
         if [[ "$testE" < "$lowestE1" ]]
           then
             lowestE3=$lowestE2
             lowestE2=$lowestE1
             lowestE1=$testE
#             echo "lowestE is now $lowestE"
         fi
         ;;
     esac
   done
   
# This section copies any polys with
# the three lowest exp_E scores to a
# file of their own.
c8=""
c7=""
c6=""
c5=""
exec <"soptset${thread}"
  while read line
    do
      case $line in
        "n: "*) n=$line
          ;;   
        "Y0: "*) Y0=$line
          ;;   
        "Y1: "*) Y1=$line
          ;;   
        "c0: "*) c0=$line
          ;;   
        "c1: "*) c1=$line
          ;;   
        "c2: "*) c2=$line
          ;;   
        "c3: "*) c3=$line
          ;;   
        "c4: "*) c4=$line
          ;;   
        "c5: "*) c5=$line
          ;;   
        "c6: "*) c6=$line
          ;;   
        "c7: "*) c7=$line
          ;;   
        "c8: "*) c8=$line
          ;;
        *"exp_E ${lowestE3}"*)
          echo "$n" >> culledset${thread}
          echo "$Y0" >> culledset${thread}
          echo "$Y1" >> culledset${thread}
          echo "$c0" >> culledset${thread}
          echo "$c1" >> culledset${thread}
          echo "$c2" >> culledset${thread}
          echo "$c3" >> culledset${thread}
          echo "$c4" >> culledset${thread}
          if [ ${#c5} -gt 0 ]
            then
              echo "$c5" >> culledset${thread}
          fi
          if [ ${#c6} -gt 0 ]
            then
              echo "$c6" >> culledset${thread}
          fi
          if [ ${#c7} -gt 0 ]
            then
              echo "$c7" >> culledset${thread}
          fi
          if [ ${#c8} -gt 0 ]
            then
              echo "$c8" >> culledset${thread}
          fi
          echo "$line" >> culledset${thread}
          echo "" >> culledset${thread}
          ;;
        *"exp_E ${lowestE2}"*)
          echo "$n" >> culledset${thread}
          echo "$Y0" >> culledset${thread}
          echo "$Y1" >> culledset${thread}
          echo "$c0" >> culledset${thread}
          echo "$c1" >> culledset${thread}
          echo "$c2" >> culledset${thread}
          echo "$c3" >> culledset${thread}
          echo "$c4" >> culledset${thread}
          if [ ${#c5} -gt 0 ]
            then
              echo "$c5" >> culledset${thread}
          fi
          if [ ${#c6} -gt 0 ]
            then
              echo "$c6" >> culledset${thread}
          fi
          if [ ${#c7} -gt 0 ]
            then
              echo "$c7" >> culledset${thread}
          fi
          if [ ${#c8} -gt 0 ]
            then
              echo "$c8" >> culledset${thread}
          fi
          echo "$line" >> culledset${thread}
          echo "" >> culledset${thread}
          ;;
        *"exp_E ${lowestE1}"*)
          echo "$n" >> culledset${thread}
          echo "$Y0" >> culledset${thread}
          echo "$Y1" >> culledset${thread}
          echo "$c0" >> culledset${thread}
          echo "$c1" >> culledset${thread}
          echo "$c2" >> culledset${thread}
          echo "$c3" >> culledset${thread}
          echo "$c4" >> culledset${thread}
          if [ ${#c5} -gt 0 ]
            then
              echo "$c5" >> culledset${thread}
          fi
          if [ ${#c6} -gt 0 ]
            then
              echo "$c6" >> culledset${thread}
          fi
          if [ ${#c7} -gt 0 ]
            then
              echo "$c7" >> culledset${thread}
          fi
          if [ ${#c8} -gt 0 ]
            then
              echo "$c8" >> culledset${thread}
          fi
          echo "$line" >> culledset${thread}
          echo "" >> culledset${thread}
          ;;
      esac
    done

# This is currently used for info purposes only
 echo "# testE is $testE (${lowestE3}, ${lowestE2}, ${lowestE1})" >> culledset${thread}

The continuation will be to add the Msieve root optimizations for each set of culled polynomials and then cull the best from each set and finally work with those for a best of the best polynomial.

More later. . .

[firejuggler]

Thank you EdH, I'm very interested in this script, as it sem to combine the best of both world.

[EdH]

Update: I now have added the Msieve rootopt for the three best scores from each sopt operation. The rootopt is done with stage2_norm going in steps from 1.0 through 9.9e<from original>. I plan to have a step value variable in case 1 is too fine. From there, the best of each process (thread) will be collected, and eventually, the top (or two or three) of those will be displayed.

Right now, I'm running a full scale test of what I have so far on the latest poly request, while I play with the newest additions.

I have not addressed any GPU use, yet. I'll have to consider where I want to add that in. Right now, it looks like that will be a totally separate set of scripts - I can't have every thread using the GPU at once.

[EdH]

Originally Posted by EdH

. . . The rootopt is done with stage2_norm going in steps from 1.0 through 9.9e<from original>. I plan to have a step value variable in case 1 is too fine.
. . .

Is this going to change the root optimization of existing polynomials or is it just going to change a cutoff for acceptable results?

[EdH]

Varying stage2_norm had no effect on -npr, as expected after rereading some things. I'm still trying to find a way to work this without modifying anyone else's program, because I'd like a solution which others users can work with, without such modifications. Perhaps this is not attainable, but I'll still try for a while. Perhaps in the end my script(s) can be the basis for others who will want to modify their versions of Msieve or such. As for now, the best combined score I turned up for the latest in the poly request thread is only 1.698e-14, well below the current leader.

[EdH]

Well, in all my testing, I have yet to turn up anything useful. I'm close to abandoning this venture, at least until I study the overall workings a bit more. As it stands this is where I've gotten.

An overall controlling script that starts a number of scripts in separate threads, chosen by the user. It then waits for all threads to complete and chooses the best of all the polys from all the threads.

The script in each thread, runs the following:

- The main Msieve -np1 -nps to gather relations
- CADO-NFS sopt on all relations from Msieve
- cull all of the three best (lowest exp_E) scoring polys from sopt
- (optional - chosen by user) CADO-NFS ropt on culled polys
- Msieve -npr on the culled set, or on the full ropt set if ropt is run.

[EdH]

My attempt to work this without Msieve modification is showing no success. I suppose to determine if that is my failure point, I will have to make the changes and run some more tests.